1 /* 2 * Copyright (c) 2005, 2010, 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/ciArrayKlass.hpp" 27 #include "ci/ciEnv.hpp" 28 #include "ci/ciKlass.hpp" 29 #include "ci/ciMethod.hpp" 30 #include "code/dependencies.hpp" 31 #include "compiler/compileLog.hpp" 32 #include "oops/oop.inline.hpp" 33 #include "runtime/handles.inline.hpp" 34 #include "utilities/copy.hpp" 35 36 37 #ifdef ASSERT 38 static bool must_be_in_vm() { 39 Thread* thread = Thread::current(); 40 if (thread->is_Java_thread()) 41 return ((JavaThread*)thread)->thread_state() == _thread_in_vm; 42 else 43 return true; //something like this: thread->is_VM_thread(); 44 } 45 #endif //ASSERT 46 47 void Dependencies::initialize(ciEnv* env) { 48 Arena* arena = env->arena(); 49 _oop_recorder = env->oop_recorder(); 50 _log = env->log(); 51 _dep_seen = new(arena) GrowableArray<int>(arena, 500, 0, 0); 52 DEBUG_ONLY(_deps[end_marker] = NULL); 53 for (int i = (int)FIRST_TYPE; i < (int)TYPE_LIMIT; i++) { 54 _deps[i] = new(arena) GrowableArray<ciObject*>(arena, 10, 0, 0); 55 } 56 _content_bytes = NULL; 57 _size_in_bytes = (size_t)-1; 58 59 assert(TYPE_LIMIT <= (1<<LG2_TYPE_LIMIT), "sanity"); 60 } 61 62 void Dependencies::assert_evol_method(ciMethod* m) { 63 assert_common_1(evol_method, m); 64 } 65 66 void Dependencies::assert_leaf_type(ciKlass* ctxk) { 67 if (ctxk->is_array_klass()) { 68 // As a special case, support this assertion on an array type, 69 // which reduces to an assertion on its element type. 70 // Note that this cannot be done with assertions that 71 // relate to concreteness or abstractness. 72 ciType* elemt = ctxk->as_array_klass()->base_element_type(); 73 if (!elemt->is_instance_klass()) return; // Ex: int[][] 74 ctxk = elemt->as_instance_klass(); 75 //if (ctxk->is_final()) return; // Ex: String[][] 76 } 77 check_ctxk(ctxk); 78 assert_common_1(leaf_type, ctxk); 79 } 80 81 void Dependencies::assert_abstract_with_unique_concrete_subtype(ciKlass* ctxk, ciKlass* conck) { 82 check_ctxk_abstract(ctxk); 83 assert_common_2(abstract_with_unique_concrete_subtype, ctxk, conck); 84 } 85 86 void Dependencies::assert_abstract_with_no_concrete_subtype(ciKlass* ctxk) { 87 check_ctxk_abstract(ctxk); 88 assert_common_1(abstract_with_no_concrete_subtype, ctxk); 89 } 90 91 void Dependencies::assert_concrete_with_no_concrete_subtype(ciKlass* ctxk) { 92 check_ctxk_concrete(ctxk); 93 assert_common_1(concrete_with_no_concrete_subtype, ctxk); 94 } 95 96 void Dependencies::assert_unique_concrete_method(ciKlass* ctxk, ciMethod* uniqm) { 97 check_ctxk(ctxk); 98 assert_common_2(unique_concrete_method, ctxk, uniqm); 99 } 100 101 void Dependencies::assert_abstract_with_exclusive_concrete_subtypes(ciKlass* ctxk, ciKlass* k1, ciKlass* k2) { 102 check_ctxk(ctxk); 103 assert_common_3(abstract_with_exclusive_concrete_subtypes_2, ctxk, k1, k2); 104 } 105 106 void Dependencies::assert_exclusive_concrete_methods(ciKlass* ctxk, ciMethod* m1, ciMethod* m2) { 107 check_ctxk(ctxk); 108 assert_common_3(exclusive_concrete_methods_2, ctxk, m1, m2); 109 } 110 111 void Dependencies::assert_has_no_finalizable_subclasses(ciKlass* ctxk) { 112 check_ctxk(ctxk); 113 assert_common_1(no_finalizable_subclasses, ctxk); 114 } 115 116 // Helper function. If we are adding a new dep. under ctxk2, 117 // try to find an old dep. under a broader* ctxk1. If there is 118 // 119 bool Dependencies::maybe_merge_ctxk(GrowableArray<ciObject*>* deps, 120 int ctxk_i, ciKlass* ctxk2) { 121 ciKlass* ctxk1 = deps->at(ctxk_i)->as_klass(); 122 if (ctxk2->is_subtype_of(ctxk1)) { 123 return true; // success, and no need to change 124 } else if (ctxk1->is_subtype_of(ctxk2)) { 125 // new context class fully subsumes previous one 126 deps->at_put(ctxk_i, ctxk2); 127 return true; 128 } else { 129 return false; 130 } 131 } 132 133 void Dependencies::assert_common_1(Dependencies::DepType dept, ciObject* x) { 134 assert(dep_args(dept) == 1, "sanity"); 135 log_dependency(dept, x); 136 GrowableArray<ciObject*>* deps = _deps[dept]; 137 138 // see if the same (or a similar) dep is already recorded 139 if (note_dep_seen(dept, x)) { 140 assert(deps->find(x) >= 0, "sanity"); 141 } else { 142 deps->append(x); 143 } 144 } 145 146 void Dependencies::assert_common_2(Dependencies::DepType dept, 147 ciKlass* ctxk, ciObject* x) { 148 assert(dep_context_arg(dept) == 0, "sanity"); 149 assert(dep_args(dept) == 2, "sanity"); 150 log_dependency(dept, ctxk, x); 151 GrowableArray<ciObject*>* deps = _deps[dept]; 152 153 // see if the same (or a similar) dep is already recorded 154 if (note_dep_seen(dept, x)) { 155 // look in this bucket for redundant assertions 156 const int stride = 2; 157 for (int i = deps->length(); (i -= stride) >= 0; ) { 158 ciObject* x1 = deps->at(i+1); 159 if (x == x1) { // same subject; check the context 160 if (maybe_merge_ctxk(deps, i+0, ctxk)) { 161 return; 162 } 163 } 164 } 165 } 166 167 // append the assertion in the correct bucket: 168 deps->append(ctxk); 169 deps->append(x); 170 } 171 172 void Dependencies::assert_common_3(Dependencies::DepType dept, 173 ciKlass* ctxk, ciObject* x, ciObject* x2) { 174 assert(dep_context_arg(dept) == 0, "sanity"); 175 assert(dep_args(dept) == 3, "sanity"); 176 log_dependency(dept, ctxk, x, x2); 177 GrowableArray<ciObject*>* deps = _deps[dept]; 178 179 // try to normalize an unordered pair: 180 bool swap = false; 181 switch (dept) { 182 case abstract_with_exclusive_concrete_subtypes_2: 183 swap = (x->ident() > x2->ident() && x != ctxk); 184 break; 185 case exclusive_concrete_methods_2: 186 swap = (x->ident() > x2->ident() && x->as_method()->holder() != ctxk); 187 break; 188 } 189 if (swap) { ciObject* t = x; x = x2; x2 = t; } 190 191 // see if the same (or a similar) dep is already recorded 192 if (note_dep_seen(dept, x) && note_dep_seen(dept, x2)) { 193 // look in this bucket for redundant assertions 194 const int stride = 3; 195 for (int i = deps->length(); (i -= stride) >= 0; ) { 196 ciObject* y = deps->at(i+1); 197 ciObject* y2 = deps->at(i+2); 198 if (x == y && x2 == y2) { // same subjects; check the context 199 if (maybe_merge_ctxk(deps, i+0, ctxk)) { 200 return; 201 } 202 } 203 } 204 } 205 // append the assertion in the correct bucket: 206 deps->append(ctxk); 207 deps->append(x); 208 deps->append(x2); 209 } 210 211 /// Support for encoding dependencies into an nmethod: 212 213 void Dependencies::copy_to(nmethod* nm) { 214 address beg = nm->dependencies_begin(); 215 address end = nm->dependencies_end(); 216 guarantee(end - beg >= (ptrdiff_t) size_in_bytes(), "bad sizing"); 217 Copy::disjoint_words((HeapWord*) content_bytes(), 218 (HeapWord*) beg, 219 size_in_bytes() / sizeof(HeapWord)); 220 assert(size_in_bytes() % sizeof(HeapWord) == 0, "copy by words"); 221 } 222 223 static int sort_dep(ciObject** p1, ciObject** p2, int narg) { 224 for (int i = 0; i < narg; i++) { 225 int diff = p1[i]->ident() - p2[i]->ident(); 226 if (diff != 0) return diff; 227 } 228 return 0; 229 } 230 static int sort_dep_arg_1(ciObject** p1, ciObject** p2) 231 { return sort_dep(p1, p2, 1); } 232 static int sort_dep_arg_2(ciObject** p1, ciObject** p2) 233 { return sort_dep(p1, p2, 2); } 234 static int sort_dep_arg_3(ciObject** p1, ciObject** p2) 235 { return sort_dep(p1, p2, 3); } 236 237 void Dependencies::sort_all_deps() { 238 for (int deptv = (int)FIRST_TYPE; deptv < (int)TYPE_LIMIT; deptv++) { 239 DepType dept = (DepType)deptv; 240 GrowableArray<ciObject*>* deps = _deps[dept]; 241 if (deps->length() <= 1) continue; 242 switch (dep_args(dept)) { 243 case 1: deps->sort(sort_dep_arg_1, 1); break; 244 case 2: deps->sort(sort_dep_arg_2, 2); break; 245 case 3: deps->sort(sort_dep_arg_3, 3); break; 246 default: ShouldNotReachHere(); 247 } 248 } 249 } 250 251 size_t Dependencies::estimate_size_in_bytes() { 252 size_t est_size = 100; 253 for (int deptv = (int)FIRST_TYPE; deptv < (int)TYPE_LIMIT; deptv++) { 254 DepType dept = (DepType)deptv; 255 GrowableArray<ciObject*>* deps = _deps[dept]; 256 est_size += deps->length()*2; // tags and argument(s) 257 } 258 return est_size; 259 } 260 261 ciKlass* Dependencies::ctxk_encoded_as_null(DepType dept, ciObject* x) { 262 switch (dept) { 263 case abstract_with_exclusive_concrete_subtypes_2: 264 return x->as_klass(); 265 case unique_concrete_method: 266 case exclusive_concrete_methods_2: 267 return x->as_method()->holder(); 268 } 269 return NULL; // let NULL be NULL 270 } 271 272 klassOop Dependencies::ctxk_encoded_as_null(DepType dept, oop x) { 273 assert(must_be_in_vm(), "raw oops here"); 274 switch (dept) { 275 case abstract_with_exclusive_concrete_subtypes_2: 276 assert(x->is_klass(), "sanity"); 277 return (klassOop) x; 278 case unique_concrete_method: 279 case exclusive_concrete_methods_2: 280 assert(x->is_method(), "sanity"); 281 return ((methodOop)x)->method_holder(); 282 } 283 return NULL; // let NULL be NULL 284 } 285 286 void Dependencies::encode_content_bytes() { 287 sort_all_deps(); 288 289 // cast is safe, no deps can overflow INT_MAX 290 CompressedWriteStream bytes((int)estimate_size_in_bytes()); 291 292 for (int deptv = (int)FIRST_TYPE; deptv < (int)TYPE_LIMIT; deptv++) { 293 DepType dept = (DepType)deptv; 294 GrowableArray<ciObject*>* deps = _deps[dept]; 295 if (deps->length() == 0) continue; 296 int stride = dep_args(dept); 297 int ctxkj = dep_context_arg(dept); // -1 if no context arg 298 assert(stride > 0, "sanity"); 299 for (int i = 0; i < deps->length(); i += stride) { 300 jbyte code_byte = (jbyte)dept; 301 int skipj = -1; 302 if (ctxkj >= 0 && ctxkj+1 < stride) { 303 ciKlass* ctxk = deps->at(i+ctxkj+0)->as_klass(); 304 ciObject* x = deps->at(i+ctxkj+1); // following argument 305 if (ctxk == ctxk_encoded_as_null(dept, x)) { 306 skipj = ctxkj; // we win: maybe one less oop to keep track of 307 code_byte |= default_context_type_bit; 308 } 309 } 310 bytes.write_byte(code_byte); 311 for (int j = 0; j < stride; j++) { 312 if (j == skipj) continue; 313 bytes.write_int(_oop_recorder->find_index(deps->at(i+j)->constant_encoding())); 314 } 315 } 316 } 317 318 // write a sentinel byte to mark the end 319 bytes.write_byte(end_marker); 320 321 // round it out to a word boundary 322 while (bytes.position() % sizeof(HeapWord) != 0) { 323 bytes.write_byte(end_marker); 324 } 325 326 // check whether the dept byte encoding really works 327 assert((jbyte)default_context_type_bit != 0, "byte overflow"); 328 329 _content_bytes = bytes.buffer(); 330 _size_in_bytes = bytes.position(); 331 } 332 333 334 const char* Dependencies::_dep_name[TYPE_LIMIT] = { 335 "end_marker", 336 "evol_method", 337 "leaf_type", 338 "abstract_with_unique_concrete_subtype", 339 "abstract_with_no_concrete_subtype", 340 "concrete_with_no_concrete_subtype", 341 "unique_concrete_method", 342 "abstract_with_exclusive_concrete_subtypes_2", 343 "exclusive_concrete_methods_2", 344 "no_finalizable_subclasses" 345 }; 346 347 int Dependencies::_dep_args[TYPE_LIMIT] = { 348 -1,// end_marker 349 1, // evol_method m 350 1, // leaf_type ctxk 351 2, // abstract_with_unique_concrete_subtype ctxk, k 352 1, // abstract_with_no_concrete_subtype ctxk 353 1, // concrete_with_no_concrete_subtype ctxk 354 2, // unique_concrete_method ctxk, m 355 3, // unique_concrete_subtypes_2 ctxk, k1, k2 356 3, // unique_concrete_methods_2 ctxk, m1, m2 357 1 // no_finalizable_subclasses ctxk 358 }; 359 360 const char* Dependencies::dep_name(Dependencies::DepType dept) { 361 if (!dept_in_mask(dept, all_types)) return "?bad-dep?"; 362 return _dep_name[dept]; 363 } 364 365 int Dependencies::dep_args(Dependencies::DepType dept) { 366 if (!dept_in_mask(dept, all_types)) return -1; 367 return _dep_args[dept]; 368 } 369 370 // for the sake of the compiler log, print out current dependencies: 371 void Dependencies::log_all_dependencies() { 372 if (log() == NULL) return; 373 ciObject* args[max_arg_count]; 374 for (int deptv = (int)FIRST_TYPE; deptv < (int)TYPE_LIMIT; deptv++) { 375 DepType dept = (DepType)deptv; 376 GrowableArray<ciObject*>* deps = _deps[dept]; 377 if (deps->length() == 0) continue; 378 int stride = dep_args(dept); 379 for (int i = 0; i < deps->length(); i += stride) { 380 for (int j = 0; j < stride; j++) { 381 // flush out the identities before printing 382 args[j] = deps->at(i+j); 383 } 384 write_dependency_to(log(), dept, stride, args); 385 } 386 } 387 } 388 389 void Dependencies::write_dependency_to(CompileLog* log, 390 DepType dept, 391 int nargs, oop args[], 392 klassOop witness) { 393 if (log == NULL) { 394 return; 395 } 396 ciEnv* env = ciEnv::current(); 397 ciObject* ciargs[max_arg_count]; 398 assert(nargs <= max_arg_count, "oob"); 399 for (int j = 0; j < nargs; j++) { 400 ciargs[j] = env->get_object(args[j]); 401 } 402 Dependencies::write_dependency_to(log, dept, nargs, ciargs, witness); 403 } 404 405 void Dependencies::write_dependency_to(CompileLog* log, 406 DepType dept, 407 int nargs, ciObject* args[], 408 klassOop witness) { 409 if (log == NULL) return; 410 assert(nargs <= max_arg_count, "oob"); 411 int argids[max_arg_count]; 412 int ctxkj = dep_context_arg(dept); // -1 if no context arg 413 int j; 414 for (j = 0; j < nargs; j++) { 415 argids[j] = log->identify(args[j]); 416 } 417 if (witness != NULL) { 418 log->begin_elem("dependency_failed"); 419 } else { 420 log->begin_elem("dependency"); 421 } 422 log->print(" type='%s'", dep_name(dept)); 423 if (ctxkj >= 0) { 424 log->print(" ctxk='%d'", argids[ctxkj]); 425 } 426 // write remaining arguments, if any. 427 for (j = 0; j < nargs; j++) { 428 if (j == ctxkj) continue; // already logged 429 if (j == 1) { 430 log->print( " x='%d'", argids[j]); 431 } else { 432 log->print(" x%d='%d'", j, argids[j]); 433 } 434 } 435 if (witness != NULL) { 436 log->object("witness", witness); 437 log->stamp(); 438 } 439 log->end_elem(); 440 } 441 442 void Dependencies::write_dependency_to(xmlStream* xtty, 443 DepType dept, 444 int nargs, oop args[], 445 klassOop witness) { 446 if (xtty == NULL) return; 447 ttyLocker ttyl; 448 int ctxkj = dep_context_arg(dept); // -1 if no context arg 449 if (witness != NULL) { 450 xtty->begin_elem("dependency_failed"); 451 } else { 452 xtty->begin_elem("dependency"); 453 } 454 xtty->print(" type='%s'", dep_name(dept)); 455 if (ctxkj >= 0) { 456 xtty->object("ctxk", args[ctxkj]); 457 } 458 // write remaining arguments, if any. 459 for (int j = 0; j < nargs; j++) { 460 if (j == ctxkj) continue; // already logged 461 if (j == 1) { 462 xtty->object("x", args[j]); 463 } else { 464 char xn[10]; sprintf(xn, "x%d", j); 465 xtty->object(xn, args[j]); 466 } 467 } 468 if (witness != NULL) { 469 xtty->object("witness", witness); 470 xtty->stamp(); 471 } 472 xtty->end_elem(); 473 } 474 475 void Dependencies::print_dependency(DepType dept, int nargs, oop args[], 476 klassOop witness) { 477 ResourceMark rm; 478 ttyLocker ttyl; // keep the following output all in one block 479 tty->print_cr("%s of type %s", 480 (witness == NULL)? "Dependency": "Failed dependency", 481 dep_name(dept)); 482 // print arguments 483 int ctxkj = dep_context_arg(dept); // -1 if no context arg 484 for (int j = 0; j < nargs; j++) { 485 oop arg = args[j]; 486 bool put_star = false; 487 if (arg == NULL) continue; 488 const char* what; 489 if (j == ctxkj) { 490 what = "context"; 491 put_star = !Dependencies::is_concrete_klass((klassOop)arg); 492 } else if (arg->is_method()) { 493 what = "method "; 494 put_star = !Dependencies::is_concrete_method((methodOop)arg); 495 } else if (arg->is_klass()) { 496 what = "class "; 497 } else { 498 what = "object "; 499 } 500 tty->print(" %s = %s", what, (put_star? "*": "")); 501 if (arg->is_klass()) 502 tty->print("%s", Klass::cast((klassOop)arg)->external_name()); 503 else 504 arg->print_value(); 505 tty->cr(); 506 } 507 if (witness != NULL) { 508 bool put_star = !Dependencies::is_concrete_klass(witness); 509 tty->print_cr(" witness = %s%s", 510 (put_star? "*": ""), 511 Klass::cast(witness)->external_name()); 512 } 513 } 514 515 void Dependencies::DepStream::log_dependency(klassOop witness) { 516 if (_deps == NULL && xtty == NULL) return; // fast cutout for runtime 517 int nargs = argument_count(); 518 oop args[max_arg_count]; 519 for (int j = 0; j < nargs; j++) { 520 args[j] = argument(j); 521 } 522 if (_deps != NULL && _deps->log() != NULL) { 523 Dependencies::write_dependency_to(_deps->log(), 524 type(), nargs, args, witness); 525 } else { 526 Dependencies::write_dependency_to(xtty, 527 type(), nargs, args, witness); 528 } 529 } 530 531 void Dependencies::DepStream::print_dependency(klassOop witness, bool verbose) { 532 int nargs = argument_count(); 533 oop args[max_arg_count]; 534 for (int j = 0; j < nargs; j++) { 535 args[j] = argument(j); 536 } 537 Dependencies::print_dependency(type(), nargs, args, witness); 538 if (verbose) { 539 if (_code != NULL) { 540 tty->print(" code: "); 541 _code->print_value_on(tty); 542 tty->cr(); 543 } 544 } 545 } 546 547 548 /// Dependency stream support (decodes dependencies from an nmethod): 549 550 #ifdef ASSERT 551 void Dependencies::DepStream::initial_asserts(size_t byte_limit) { 552 assert(must_be_in_vm(), "raw oops here"); 553 _byte_limit = byte_limit; 554 _type = (DepType)(end_marker-1); // defeat "already at end" assert 555 assert((_code!=NULL) + (_deps!=NULL) == 1, "one or t'other"); 556 } 557 #endif //ASSERT 558 559 bool Dependencies::DepStream::next() { 560 assert(_type != end_marker, "already at end"); 561 if (_bytes.position() == 0 && _code != NULL 562 && _code->dependencies_size() == 0) { 563 // Method has no dependencies at all. 564 return false; 565 } 566 int code_byte = (_bytes.read_byte() & 0xFF); 567 if (code_byte == end_marker) { 568 DEBUG_ONLY(_type = end_marker); 569 return false; 570 } else { 571 int ctxk_bit = (code_byte & Dependencies::default_context_type_bit); 572 code_byte -= ctxk_bit; 573 DepType dept = (DepType)code_byte; 574 _type = dept; 575 guarantee((dept - FIRST_TYPE) < (TYPE_LIMIT - FIRST_TYPE), 576 "bad dependency type tag"); 577 int stride = _dep_args[dept]; 578 assert(stride == dep_args(dept), "sanity"); 579 int skipj = -1; 580 if (ctxk_bit != 0) { 581 skipj = 0; // currently the only context argument is at zero 582 assert(skipj == dep_context_arg(dept), "zero arg always ctxk"); 583 } 584 for (int j = 0; j < stride; j++) { 585 _xi[j] = (j == skipj)? 0: _bytes.read_int(); 586 } 587 DEBUG_ONLY(_xi[stride] = -1); // help detect overruns 588 return true; 589 } 590 } 591 592 inline oop Dependencies::DepStream::recorded_oop_at(int i) { 593 return (_code != NULL) 594 ? _code->oop_at(i) 595 : JNIHandles::resolve(_deps->oop_recorder()->handle_at(i)); 596 } 597 598 oop Dependencies::DepStream::argument(int i) { 599 return recorded_oop_at(argument_index(i)); 600 } 601 602 klassOop Dependencies::DepStream::context_type() { 603 assert(must_be_in_vm(), "raw oops here"); 604 int ctxkj = dep_context_arg(_type); // -1 if no context arg 605 if (ctxkj < 0) { 606 return NULL; // for example, evol_method 607 } else { 608 oop k = recorded_oop_at(_xi[ctxkj]); 609 if (k != NULL) { // context type was not compressed away 610 assert(k->is_klass(), "type check"); 611 return (klassOop) k; 612 } else { // recompute "default" context type 613 return ctxk_encoded_as_null(_type, recorded_oop_at(_xi[ctxkj+1])); 614 } 615 } 616 } 617 618 /// Checking dependencies: 619 620 // This hierarchy walker inspects subtypes of a given type, 621 // trying to find a "bad" class which breaks a dependency. 622 // Such a class is called a "witness" to the broken dependency. 623 // While searching around, we ignore "participants", which 624 // are already known to the dependency. 625 class ClassHierarchyWalker { 626 public: 627 enum { PARTICIPANT_LIMIT = 3 }; 628 629 private: 630 // optional method descriptor to check for: 631 symbolOop _name; 632 symbolOop _signature; 633 634 // special classes which are not allowed to be witnesses: 635 klassOop _participants[PARTICIPANT_LIMIT+1]; 636 int _num_participants; 637 638 // cache of method lookups 639 methodOop _found_methods[PARTICIPANT_LIMIT+1]; 640 641 // if non-zero, tells how many witnesses to convert to participants 642 int _record_witnesses; 643 644 void initialize(klassOop participant) { 645 _record_witnesses = 0; 646 _participants[0] = participant; 647 _found_methods[0] = NULL; 648 _num_participants = 0; 649 if (participant != NULL) { 650 // Terminating NULL. 651 _participants[1] = NULL; 652 _found_methods[1] = NULL; 653 _num_participants = 1; 654 } 655 } 656 657 void initialize_from_method(methodOop m) { 658 assert(m != NULL && m->is_method(), "sanity"); 659 _name = m->name(); 660 _signature = m->signature(); 661 } 662 663 public: 664 // The walker is initialized to recognize certain methods and/or types 665 // as friendly participants. 666 ClassHierarchyWalker(klassOop participant, methodOop m) { 667 initialize_from_method(m); 668 initialize(participant); 669 } 670 ClassHierarchyWalker(methodOop m) { 671 initialize_from_method(m); 672 initialize(NULL); 673 } 674 ClassHierarchyWalker(klassOop participant = NULL) { 675 _name = NULL; 676 _signature = NULL; 677 initialize(participant); 678 } 679 680 // This is common code for two searches: One for concrete subtypes, 681 // the other for concrete method implementations and overrides. 682 bool doing_subtype_search() { 683 return _name == NULL; 684 } 685 686 int num_participants() { return _num_participants; } 687 klassOop participant(int n) { 688 assert((uint)n <= (uint)_num_participants, "oob"); 689 return _participants[n]; 690 } 691 692 // Note: If n==num_participants, returns NULL. 693 methodOop found_method(int n) { 694 assert((uint)n <= (uint)_num_participants, "oob"); 695 methodOop fm = _found_methods[n]; 696 assert(n == _num_participants || fm != NULL, "proper usage"); 697 assert(fm == NULL || fm->method_holder() == _participants[n], "sanity"); 698 return fm; 699 } 700 701 #ifdef ASSERT 702 // Assert that m is inherited into ctxk, without intervening overrides. 703 // (May return true even if this is not true, in corner cases where we punt.) 704 bool check_method_context(klassOop ctxk, methodOop m) { 705 if (m->method_holder() == ctxk) 706 return true; // Quick win. 707 if (m->is_private()) 708 return false; // Quick lose. Should not happen. 709 if (!(m->is_public() || m->is_protected())) 710 // The override story is complex when packages get involved. 711 return true; // Must punt the assertion to true. 712 Klass* k = Klass::cast(ctxk); 713 methodOop lm = k->lookup_method(m->name(), m->signature()); 714 if (lm == NULL && k->oop_is_instance()) { 715 // It might be an abstract interface method, devoid of mirandas. 716 lm = ((instanceKlass*)k)->lookup_method_in_all_interfaces(m->name(), 717 m->signature()); 718 } 719 if (lm == m) 720 // Method m is inherited into ctxk. 721 return true; 722 if (lm != NULL) { 723 if (!(lm->is_public() || lm->is_protected())) 724 // Method is [package-]private, so the override story is complex. 725 return true; // Must punt the assertion to true. 726 if ( !Dependencies::is_concrete_method(lm) 727 && !Dependencies::is_concrete_method(m) 728 && Klass::cast(lm->method_holder())->is_subtype_of(m->method_holder())) 729 // Method m is overridden by lm, but both are non-concrete. 730 return true; 731 } 732 ResourceMark rm; 733 tty->print_cr("Dependency method not found in the associated context:"); 734 tty->print_cr(" context = %s", Klass::cast(ctxk)->external_name()); 735 tty->print( " method = "); m->print_short_name(tty); tty->cr(); 736 if (lm != NULL) { 737 tty->print( " found = "); lm->print_short_name(tty); tty->cr(); 738 } 739 return false; 740 } 741 #endif 742 743 void add_participant(klassOop participant) { 744 assert(_num_participants + _record_witnesses < PARTICIPANT_LIMIT, "oob"); 745 int np = _num_participants++; 746 _participants[np] = participant; 747 _participants[np+1] = NULL; 748 _found_methods[np+1] = NULL; 749 } 750 751 void record_witnesses(int add) { 752 if (add > PARTICIPANT_LIMIT) add = PARTICIPANT_LIMIT; 753 assert(_num_participants + add < PARTICIPANT_LIMIT, "oob"); 754 _record_witnesses = add; 755 } 756 757 bool is_witness(klassOop k) { 758 if (doing_subtype_search()) { 759 return Dependencies::is_concrete_klass(k); 760 } else { 761 methodOop m = instanceKlass::cast(k)->find_method(_name, _signature); 762 if (m == NULL || !Dependencies::is_concrete_method(m)) return false; 763 _found_methods[_num_participants] = m; 764 // Note: If add_participant(k) is called, 765 // the method m will already be memoized for it. 766 return true; 767 } 768 } 769 770 bool is_participant(klassOop k) { 771 if (k == _participants[0]) { 772 return true; 773 } else if (_num_participants <= 1) { 774 return false; 775 } else { 776 return in_list(k, &_participants[1]); 777 } 778 } 779 bool ignore_witness(klassOop witness) { 780 if (_record_witnesses == 0) { 781 return false; 782 } else { 783 --_record_witnesses; 784 add_participant(witness); 785 return true; 786 } 787 } 788 static bool in_list(klassOop x, klassOop* list) { 789 for (int i = 0; ; i++) { 790 klassOop y = list[i]; 791 if (y == NULL) break; 792 if (y == x) return true; 793 } 794 return false; // not in list 795 } 796 797 private: 798 // the actual search method: 799 klassOop find_witness_anywhere(klassOop context_type, 800 bool participants_hide_witnesses, 801 bool top_level_call = true); 802 // the spot-checking version: 803 klassOop find_witness_in(DepChange& changes, 804 klassOop context_type, 805 bool participants_hide_witnesses); 806 public: 807 klassOop find_witness_subtype(klassOop context_type, DepChange* changes = NULL) { 808 assert(doing_subtype_search(), "must set up a subtype search"); 809 // When looking for unexpected concrete types, 810 // do not look beneath expected ones. 811 const bool participants_hide_witnesses = true; 812 // CX > CC > C' is OK, even if C' is new. 813 // CX > { CC, C' } is not OK if C' is new, and C' is the witness. 814 if (changes != NULL) { 815 return find_witness_in(*changes, context_type, participants_hide_witnesses); 816 } else { 817 return find_witness_anywhere(context_type, participants_hide_witnesses); 818 } 819 } 820 klassOop find_witness_definer(klassOop context_type, DepChange* changes = NULL) { 821 assert(!doing_subtype_search(), "must set up a method definer search"); 822 // When looking for unexpected concrete methods, 823 // look beneath expected ones, to see if there are overrides. 824 const bool participants_hide_witnesses = true; 825 // CX.m > CC.m > C'.m is not OK, if C'.m is new, and C' is the witness. 826 if (changes != NULL) { 827 return find_witness_in(*changes, context_type, !participants_hide_witnesses); 828 } else { 829 return find_witness_anywhere(context_type, !participants_hide_witnesses); 830 } 831 } 832 }; 833 834 #ifndef PRODUCT 835 static int deps_find_witness_calls = 0; 836 static int deps_find_witness_steps = 0; 837 static int deps_find_witness_recursions = 0; 838 static int deps_find_witness_singles = 0; 839 static int deps_find_witness_print = 0; // set to -1 to force a final print 840 static bool count_find_witness_calls() { 841 if (TraceDependencies || LogCompilation) { 842 int pcount = deps_find_witness_print + 1; 843 bool final_stats = (pcount == 0); 844 bool initial_call = (pcount == 1); 845 bool occasional_print = ((pcount & ((1<<10) - 1)) == 0); 846 if (pcount < 0) pcount = 1; // crude overflow protection 847 deps_find_witness_print = pcount; 848 if (VerifyDependencies && initial_call) { 849 tty->print_cr("Warning: TraceDependencies results may be inflated by VerifyDependencies"); 850 } 851 if (occasional_print || final_stats) { 852 // Every now and then dump a little info about dependency searching. 853 if (xtty != NULL) { 854 ttyLocker ttyl; 855 xtty->elem("deps_find_witness calls='%d' steps='%d' recursions='%d' singles='%d'", 856 deps_find_witness_calls, 857 deps_find_witness_steps, 858 deps_find_witness_recursions, 859 deps_find_witness_singles); 860 } 861 if (final_stats || (TraceDependencies && WizardMode)) { 862 ttyLocker ttyl; 863 tty->print_cr("Dependency check (find_witness) " 864 "calls=%d, steps=%d (avg=%.1f), recursions=%d, singles=%d", 865 deps_find_witness_calls, 866 deps_find_witness_steps, 867 (double)deps_find_witness_steps / deps_find_witness_calls, 868 deps_find_witness_recursions, 869 deps_find_witness_singles); 870 } 871 } 872 return true; 873 } 874 return false; 875 } 876 #else 877 #define count_find_witness_calls() (0) 878 #endif //PRODUCT 879 880 881 klassOop ClassHierarchyWalker::find_witness_in(DepChange& changes, 882 klassOop context_type, 883 bool participants_hide_witnesses) { 884 assert(changes.involves_context(context_type), "irrelevant dependency"); 885 klassOop new_type = changes.new_type(); 886 887 count_find_witness_calls(); 888 NOT_PRODUCT(deps_find_witness_singles++); 889 890 // Current thread must be in VM (not native mode, as in CI): 891 assert(must_be_in_vm(), "raw oops here"); 892 // Must not move the class hierarchy during this check: 893 assert_locked_or_safepoint(Compile_lock); 894 895 int nof_impls = instanceKlass::cast(context_type)->nof_implementors(); 896 if (nof_impls > 1) { 897 // Avoid this case: *I.m > { A.m, C }; B.m > C 898 // %%% Until this is fixed more systematically, bail out. 899 // See corresponding comment in find_witness_anywhere. 900 return context_type; 901 } 902 903 assert(!is_participant(new_type), "only old classes are participants"); 904 if (participants_hide_witnesses) { 905 // If the new type is a subtype of a participant, we are done. 906 for (int i = 0; i < num_participants(); i++) { 907 klassOop part = participant(i); 908 if (part == NULL) continue; 909 assert(changes.involves_context(part) == Klass::cast(new_type)->is_subtype_of(part), 910 "correct marking of participants, b/c new_type is unique"); 911 if (changes.involves_context(part)) { 912 // new guy is protected from this check by previous participant 913 return NULL; 914 } 915 } 916 } 917 918 if (is_witness(new_type) && 919 !ignore_witness(new_type)) { 920 return new_type; 921 } 922 923 return NULL; 924 } 925 926 927 // Walk hierarchy under a context type, looking for unexpected types. 928 // Do not report participant types, and recursively walk beneath 929 // them only if participants_hide_witnesses is false. 930 // If top_level_call is false, skip testing the context type, 931 // because the caller has already considered it. 932 klassOop ClassHierarchyWalker::find_witness_anywhere(klassOop context_type, 933 bool participants_hide_witnesses, 934 bool top_level_call) { 935 // Current thread must be in VM (not native mode, as in CI): 936 assert(must_be_in_vm(), "raw oops here"); 937 // Must not move the class hierarchy during this check: 938 assert_locked_or_safepoint(Compile_lock); 939 940 bool do_counts = count_find_witness_calls(); 941 942 // Check the root of the sub-hierarchy first. 943 if (top_level_call) { 944 if (do_counts) { 945 NOT_PRODUCT(deps_find_witness_calls++); 946 NOT_PRODUCT(deps_find_witness_steps++); 947 } 948 if (is_participant(context_type)) { 949 if (participants_hide_witnesses) return NULL; 950 // else fall through to search loop... 951 } else if (is_witness(context_type) && !ignore_witness(context_type)) { 952 // The context is an abstract class or interface, to start with. 953 return context_type; 954 } 955 } 956 957 // Now we must check each implementor and each subclass. 958 // Use a short worklist to avoid blowing the stack. 959 // Each worklist entry is a *chain* of subklass siblings to process. 960 const int CHAINMAX = 100; // >= 1 + instanceKlass::implementors_limit 961 Klass* chains[CHAINMAX]; 962 int chaini = 0; // index into worklist 963 Klass* chain; // scratch variable 964 #define ADD_SUBCLASS_CHAIN(k) { \ 965 assert(chaini < CHAINMAX, "oob"); \ 966 chain = instanceKlass::cast(k)->subklass(); \ 967 if (chain != NULL) chains[chaini++] = chain; } 968 969 // Look for non-abstract subclasses. 970 // (Note: Interfaces do not have subclasses.) 971 ADD_SUBCLASS_CHAIN(context_type); 972 973 // If it is an interface, search its direct implementors. 974 // (Their subclasses are additional indirect implementors. 975 // See instanceKlass::add_implementor.) 976 // (Note: nof_implementors is always zero for non-interfaces.) 977 int nof_impls = instanceKlass::cast(context_type)->nof_implementors(); 978 if (nof_impls > 1) { 979 // Avoid this case: *I.m > { A.m, C }; B.m > C 980 // Here, I.m has 2 concrete implementations, but m appears unique 981 // as A.m, because the search misses B.m when checking C. 982 // The inherited method B.m was getting missed by the walker 983 // when interface 'I' was the starting point. 984 // %%% Until this is fixed more systematically, bail out. 985 // (Old CHA had the same limitation.) 986 return context_type; 987 } 988 for (int i = 0; i < nof_impls; i++) { 989 klassOop impl = instanceKlass::cast(context_type)->implementor(i); 990 if (impl == NULL) { 991 // implementors array overflowed => no exact info. 992 return context_type; // report an inexact witness to this sad affair 993 } 994 if (do_counts) 995 { NOT_PRODUCT(deps_find_witness_steps++); } 996 if (is_participant(impl)) { 997 if (participants_hide_witnesses) continue; 998 // else fall through to process this guy's subclasses 999 } else if (is_witness(impl) && !ignore_witness(impl)) { 1000 return impl; 1001 } 1002 ADD_SUBCLASS_CHAIN(impl); 1003 } 1004 1005 // Recursively process each non-trivial sibling chain. 1006 while (chaini > 0) { 1007 Klass* chain = chains[--chaini]; 1008 for (Klass* subk = chain; subk != NULL; subk = subk->next_sibling()) { 1009 klassOop sub = subk->as_klassOop(); 1010 if (do_counts) { NOT_PRODUCT(deps_find_witness_steps++); } 1011 if (is_participant(sub)) { 1012 if (participants_hide_witnesses) continue; 1013 // else fall through to process this guy's subclasses 1014 } else if (is_witness(sub) && !ignore_witness(sub)) { 1015 return sub; 1016 } 1017 if (chaini < (VerifyDependencies? 2: CHAINMAX)) { 1018 // Fast path. (Partially disabled if VerifyDependencies.) 1019 ADD_SUBCLASS_CHAIN(sub); 1020 } else { 1021 // Worklist overflow. Do a recursive call. Should be rare. 1022 // The recursive call will have its own worklist, of course. 1023 // (Note that sub has already been tested, so that there is 1024 // no need for the recursive call to re-test. That's handy, 1025 // since the recursive call sees sub as the context_type.) 1026 if (do_counts) { NOT_PRODUCT(deps_find_witness_recursions++); } 1027 klassOop witness = find_witness_anywhere(sub, 1028 participants_hide_witnesses, 1029 /*top_level_call=*/ false); 1030 if (witness != NULL) return witness; 1031 } 1032 } 1033 } 1034 1035 // No witness found. The dependency remains unbroken. 1036 return NULL; 1037 #undef ADD_SUBCLASS_CHAIN 1038 } 1039 1040 1041 bool Dependencies::is_concrete_klass(klassOop k) { 1042 if (Klass::cast(k)->is_abstract()) return false; 1043 // %%% We could treat classes which are concrete but 1044 // have not yet been instantiated as virtually abstract. 1045 // This would require a deoptimization barrier on first instantiation. 1046 //if (k->is_not_instantiated()) return false; 1047 return true; 1048 } 1049 1050 bool Dependencies::is_concrete_method(methodOop m) { 1051 if (m->is_abstract()) return false; 1052 // %%% We could treat unexecuted methods as virtually abstract also. 1053 // This would require a deoptimization barrier on first execution. 1054 return !m->is_abstract(); 1055 } 1056 1057 1058 Klass* Dependencies::find_finalizable_subclass(Klass* k) { 1059 if (k->is_interface()) return NULL; 1060 if (k->has_finalizer()) return k; 1061 k = k->subklass(); 1062 while (k != NULL) { 1063 Klass* result = find_finalizable_subclass(k); 1064 if (result != NULL) return result; 1065 k = k->next_sibling(); 1066 } 1067 return NULL; 1068 } 1069 1070 1071 bool Dependencies::is_concrete_klass(ciInstanceKlass* k) { 1072 if (k->is_abstract()) return false; 1073 // We could return also false if k does not yet appear to be 1074 // instantiated, if the VM version supports this distinction also. 1075 //if (k->is_not_instantiated()) return false; 1076 return true; 1077 } 1078 1079 bool Dependencies::is_concrete_method(ciMethod* m) { 1080 // Statics are irrelevant to virtual call sites. 1081 if (m->is_static()) return false; 1082 1083 // We could return also false if m does not yet appear to be 1084 // executed, if the VM version supports this distinction also. 1085 return !m->is_abstract(); 1086 } 1087 1088 1089 bool Dependencies::has_finalizable_subclass(ciInstanceKlass* k) { 1090 return k->has_finalizable_subclass(); 1091 } 1092 1093 1094 // Any use of the contents (bytecodes) of a method must be 1095 // marked by an "evol_method" dependency, if those contents 1096 // can change. (Note: A method is always dependent on itself.) 1097 klassOop Dependencies::check_evol_method(methodOop m) { 1098 assert(must_be_in_vm(), "raw oops here"); 1099 // Did somebody do a JVMTI RedefineClasses while our backs were turned? 1100 // Or is there a now a breakpoint? 1101 // (Assumes compiled code cannot handle bkpts; change if UseFastBreakpoints.) 1102 if (m->is_old() 1103 || m->number_of_breakpoints() > 0) { 1104 return m->method_holder(); 1105 } else { 1106 return NULL; 1107 } 1108 } 1109 1110 // This is a strong assertion: It is that the given type 1111 // has no subtypes whatever. It is most useful for 1112 // optimizing checks on reflected types or on array types. 1113 // (Checks on types which are derived from real instances 1114 // can be optimized more strongly than this, because we 1115 // know that the checked type comes from a concrete type, 1116 // and therefore we can disregard abstract types.) 1117 klassOop Dependencies::check_leaf_type(klassOop ctxk) { 1118 assert(must_be_in_vm(), "raw oops here"); 1119 assert_locked_or_safepoint(Compile_lock); 1120 instanceKlass* ctx = instanceKlass::cast(ctxk); 1121 Klass* sub = ctx->subklass(); 1122 if (sub != NULL) { 1123 return sub->as_klassOop(); 1124 } else if (ctx->nof_implementors() != 0) { 1125 // if it is an interface, it must be unimplemented 1126 // (if it is not an interface, nof_implementors is always zero) 1127 klassOop impl = ctx->implementor(0); 1128 return (impl != NULL)? impl: ctxk; 1129 } else { 1130 return NULL; 1131 } 1132 } 1133 1134 // Test the assertion that conck is the only concrete subtype* of ctxk. 1135 // The type conck itself is allowed to have have further concrete subtypes. 1136 // This allows the compiler to narrow occurrences of ctxk by conck, 1137 // when dealing with the types of actual instances. 1138 klassOop Dependencies::check_abstract_with_unique_concrete_subtype(klassOop ctxk, 1139 klassOop conck, 1140 DepChange* changes) { 1141 ClassHierarchyWalker wf(conck); 1142 return wf.find_witness_subtype(ctxk, changes); 1143 } 1144 1145 // If a non-concrete class has no concrete subtypes, it is not (yet) 1146 // instantiatable. This can allow the compiler to make some paths go 1147 // dead, if they are gated by a test of the type. 1148 klassOop Dependencies::check_abstract_with_no_concrete_subtype(klassOop ctxk, 1149 DepChange* changes) { 1150 // Find any concrete subtype, with no participants: 1151 ClassHierarchyWalker wf; 1152 return wf.find_witness_subtype(ctxk, changes); 1153 } 1154 1155 1156 // If a concrete class has no concrete subtypes, it can always be 1157 // exactly typed. This allows the use of a cheaper type test. 1158 klassOop Dependencies::check_concrete_with_no_concrete_subtype(klassOop ctxk, 1159 DepChange* changes) { 1160 // Find any concrete subtype, with only the ctxk as participant: 1161 ClassHierarchyWalker wf(ctxk); 1162 return wf.find_witness_subtype(ctxk, changes); 1163 } 1164 1165 1166 // Find the unique concrete proper subtype of ctxk, or NULL if there 1167 // is more than one concrete proper subtype. If there are no concrete 1168 // proper subtypes, return ctxk itself, whether it is concrete or not. 1169 // The returned subtype is allowed to have have further concrete subtypes. 1170 // That is, return CC1 for CX > CC1 > CC2, but NULL for CX > { CC1, CC2 }. 1171 klassOop Dependencies::find_unique_concrete_subtype(klassOop ctxk) { 1172 ClassHierarchyWalker wf(ctxk); // Ignore ctxk when walking. 1173 wf.record_witnesses(1); // Record one other witness when walking. 1174 klassOop wit = wf.find_witness_subtype(ctxk); 1175 if (wit != NULL) return NULL; // Too many witnesses. 1176 klassOop conck = wf.participant(0); 1177 if (conck == NULL) { 1178 #ifndef PRODUCT 1179 // Make sure the dependency mechanism will pass this discovery: 1180 if (VerifyDependencies) { 1181 // Turn off dependency tracing while actually testing deps. 1182 FlagSetting fs(TraceDependencies, false); 1183 if (!Dependencies::is_concrete_klass(ctxk)) { 1184 guarantee(NULL == 1185 (void *)check_abstract_with_no_concrete_subtype(ctxk), 1186 "verify dep."); 1187 } else { 1188 guarantee(NULL == 1189 (void *)check_concrete_with_no_concrete_subtype(ctxk), 1190 "verify dep."); 1191 } 1192 } 1193 #endif //PRODUCT 1194 return ctxk; // Return ctxk as a flag for "no subtypes". 1195 } else { 1196 #ifndef PRODUCT 1197 // Make sure the dependency mechanism will pass this discovery: 1198 if (VerifyDependencies) { 1199 // Turn off dependency tracing while actually testing deps. 1200 FlagSetting fs(TraceDependencies, false); 1201 if (!Dependencies::is_concrete_klass(ctxk)) { 1202 guarantee(NULL == (void *) 1203 check_abstract_with_unique_concrete_subtype(ctxk, conck), 1204 "verify dep."); 1205 } 1206 } 1207 #endif //PRODUCT 1208 return conck; 1209 } 1210 } 1211 1212 // Test the assertion that the k[12] are the only concrete subtypes of ctxk, 1213 // except possibly for further subtypes of k[12] themselves. 1214 // The context type must be abstract. The types k1 and k2 are themselves 1215 // allowed to have further concrete subtypes. 1216 klassOop Dependencies::check_abstract_with_exclusive_concrete_subtypes( 1217 klassOop ctxk, 1218 klassOop k1, 1219 klassOop k2, 1220 DepChange* changes) { 1221 ClassHierarchyWalker wf; 1222 wf.add_participant(k1); 1223 wf.add_participant(k2); 1224 return wf.find_witness_subtype(ctxk, changes); 1225 } 1226 1227 // Search ctxk for concrete implementations. If there are klen or fewer, 1228 // pack them into the given array and return the number. 1229 // Otherwise, return -1, meaning the given array would overflow. 1230 // (Note that a return of 0 means there are exactly no concrete subtypes.) 1231 // In this search, if ctxk is concrete, it will be reported alone. 1232 // For any type CC reported, no proper subtypes of CC will be reported. 1233 int Dependencies::find_exclusive_concrete_subtypes(klassOop ctxk, 1234 int klen, 1235 klassOop karray[]) { 1236 ClassHierarchyWalker wf; 1237 wf.record_witnesses(klen); 1238 klassOop wit = wf.find_witness_subtype(ctxk); 1239 if (wit != NULL) return -1; // Too many witnesses. 1240 int num = wf.num_participants(); 1241 assert(num <= klen, "oob"); 1242 // Pack the result array with the good news. 1243 for (int i = 0; i < num; i++) 1244 karray[i] = wf.participant(i); 1245 #ifndef PRODUCT 1246 // Make sure the dependency mechanism will pass this discovery: 1247 if (VerifyDependencies) { 1248 // Turn off dependency tracing while actually testing deps. 1249 FlagSetting fs(TraceDependencies, false); 1250 switch (Dependencies::is_concrete_klass(ctxk)? -1: num) { 1251 case -1: // ctxk was itself concrete 1252 guarantee(num == 1 && karray[0] == ctxk, "verify dep."); 1253 break; 1254 case 0: 1255 guarantee(NULL == (void *)check_abstract_with_no_concrete_subtype(ctxk), 1256 "verify dep."); 1257 break; 1258 case 1: 1259 guarantee(NULL == (void *) 1260 check_abstract_with_unique_concrete_subtype(ctxk, karray[0]), 1261 "verify dep."); 1262 break; 1263 case 2: 1264 guarantee(NULL == (void *) 1265 check_abstract_with_exclusive_concrete_subtypes(ctxk, 1266 karray[0], 1267 karray[1]), 1268 "verify dep."); 1269 break; 1270 default: 1271 ShouldNotReachHere(); // klen > 2 yet supported 1272 } 1273 } 1274 #endif //PRODUCT 1275 return num; 1276 } 1277 1278 // If a class (or interface) has a unique concrete method uniqm, return NULL. 1279 // Otherwise, return a class that contains an interfering method. 1280 klassOop Dependencies::check_unique_concrete_method(klassOop ctxk, methodOop uniqm, 1281 DepChange* changes) { 1282 // Here is a missing optimization: If uniqm->is_final(), 1283 // we don't really need to search beneath it for overrides. 1284 // This is probably not important, since we don't use dependencies 1285 // to track final methods. (They can't be "definalized".) 1286 ClassHierarchyWalker wf(uniqm->method_holder(), uniqm); 1287 return wf.find_witness_definer(ctxk, changes); 1288 } 1289 1290 // Find the set of all non-abstract methods under ctxk that match m. 1291 // (The method m must be defined or inherited in ctxk.) 1292 // Include m itself in the set, unless it is abstract. 1293 // If this set has exactly one element, return that element. 1294 methodOop Dependencies::find_unique_concrete_method(klassOop ctxk, methodOop m) { 1295 ClassHierarchyWalker wf(m); 1296 assert(wf.check_method_context(ctxk, m), "proper context"); 1297 wf.record_witnesses(1); 1298 klassOop wit = wf.find_witness_definer(ctxk); 1299 if (wit != NULL) return NULL; // Too many witnesses. 1300 methodOop fm = wf.found_method(0); // Will be NULL if num_parts == 0. 1301 if (Dependencies::is_concrete_method(m)) { 1302 if (fm == NULL) { 1303 // It turns out that m was always the only implementation. 1304 fm = m; 1305 } else if (fm != m) { 1306 // Two conflicting implementations after all. 1307 // (This can happen if m is inherited into ctxk and fm overrides it.) 1308 return NULL; 1309 } 1310 } 1311 #ifndef PRODUCT 1312 // Make sure the dependency mechanism will pass this discovery: 1313 if (VerifyDependencies && fm != NULL) { 1314 guarantee(NULL == (void *)check_unique_concrete_method(ctxk, fm), 1315 "verify dep."); 1316 } 1317 #endif //PRODUCT 1318 return fm; 1319 } 1320 1321 klassOop Dependencies::check_exclusive_concrete_methods(klassOop ctxk, 1322 methodOop m1, 1323 methodOop m2, 1324 DepChange* changes) { 1325 ClassHierarchyWalker wf(m1); 1326 wf.add_participant(m1->method_holder()); 1327 wf.add_participant(m2->method_holder()); 1328 return wf.find_witness_definer(ctxk, changes); 1329 } 1330 1331 // Find the set of all non-abstract methods under ctxk that match m[0]. 1332 // (The method m[0] must be defined or inherited in ctxk.) 1333 // Include m itself in the set, unless it is abstract. 1334 // Fill the given array m[0..(mlen-1)] with this set, and return the length. 1335 // (The length may be zero if no concrete methods are found anywhere.) 1336 // If there are too many concrete methods to fit in marray, return -1. 1337 int Dependencies::find_exclusive_concrete_methods(klassOop ctxk, 1338 int mlen, 1339 methodOop marray[]) { 1340 methodOop m0 = marray[0]; 1341 ClassHierarchyWalker wf(m0); 1342 assert(wf.check_method_context(ctxk, m0), "proper context"); 1343 wf.record_witnesses(mlen); 1344 bool participants_hide_witnesses = true; 1345 klassOop wit = wf.find_witness_definer(ctxk); 1346 if (wit != NULL) return -1; // Too many witnesses. 1347 int num = wf.num_participants(); 1348 assert(num <= mlen, "oob"); 1349 // Keep track of whether m is also part of the result set. 1350 int mfill = 0; 1351 assert(marray[mfill] == m0, "sanity"); 1352 if (Dependencies::is_concrete_method(m0)) 1353 mfill++; // keep m0 as marray[0], the first result 1354 for (int i = 0; i < num; i++) { 1355 methodOop fm = wf.found_method(i); 1356 if (fm == m0) continue; // Already put this guy in the list. 1357 if (mfill == mlen) { 1358 return -1; // Oops. Too many methods after all! 1359 } 1360 marray[mfill++] = fm; 1361 } 1362 #ifndef PRODUCT 1363 // Make sure the dependency mechanism will pass this discovery: 1364 if (VerifyDependencies) { 1365 // Turn off dependency tracing while actually testing deps. 1366 FlagSetting fs(TraceDependencies, false); 1367 switch (mfill) { 1368 case 1: 1369 guarantee(NULL == (void *)check_unique_concrete_method(ctxk, marray[0]), 1370 "verify dep."); 1371 break; 1372 case 2: 1373 guarantee(NULL == (void *) 1374 check_exclusive_concrete_methods(ctxk, marray[0], marray[1]), 1375 "verify dep."); 1376 break; 1377 default: 1378 ShouldNotReachHere(); // mlen > 2 yet supported 1379 } 1380 } 1381 #endif //PRODUCT 1382 return mfill; 1383 } 1384 1385 1386 klassOop Dependencies::check_has_no_finalizable_subclasses(klassOop ctxk, DepChange* changes) { 1387 Klass* search_at = ctxk->klass_part(); 1388 if (changes != NULL) 1389 search_at = changes->new_type()->klass_part(); // just look at the new bit 1390 Klass* result = find_finalizable_subclass(search_at); 1391 if (result == NULL) { 1392 return NULL; 1393 } 1394 return result->as_klassOop(); 1395 } 1396 1397 1398 klassOop Dependencies::DepStream::check_dependency_impl(DepChange* changes) { 1399 assert_locked_or_safepoint(Compile_lock); 1400 1401 klassOop witness = NULL; 1402 switch (type()) { 1403 case evol_method: 1404 witness = check_evol_method(method_argument(0)); 1405 break; 1406 case leaf_type: 1407 witness = check_leaf_type(context_type()); 1408 break; 1409 case abstract_with_unique_concrete_subtype: 1410 witness = check_abstract_with_unique_concrete_subtype(context_type(), 1411 type_argument(1), 1412 changes); 1413 break; 1414 case abstract_with_no_concrete_subtype: 1415 witness = check_abstract_with_no_concrete_subtype(context_type(), 1416 changes); 1417 break; 1418 case concrete_with_no_concrete_subtype: 1419 witness = check_concrete_with_no_concrete_subtype(context_type(), 1420 changes); 1421 break; 1422 case unique_concrete_method: 1423 witness = check_unique_concrete_method(context_type(), 1424 method_argument(1), 1425 changes); 1426 break; 1427 case abstract_with_exclusive_concrete_subtypes_2: 1428 witness = check_abstract_with_exclusive_concrete_subtypes(context_type(), 1429 type_argument(1), 1430 type_argument(2), 1431 changes); 1432 break; 1433 case exclusive_concrete_methods_2: 1434 witness = check_exclusive_concrete_methods(context_type(), 1435 method_argument(1), 1436 method_argument(2), 1437 changes); 1438 break; 1439 case no_finalizable_subclasses: 1440 witness = check_has_no_finalizable_subclasses(context_type(), 1441 changes); 1442 break; 1443 default: 1444 witness = NULL; 1445 ShouldNotReachHere(); 1446 break; 1447 } 1448 if (witness != NULL) { 1449 if (TraceDependencies) { 1450 print_dependency(witness, /*verbose=*/ true); 1451 } 1452 // The following is a no-op unless logging is enabled: 1453 log_dependency(witness); 1454 } 1455 return witness; 1456 } 1457 1458 1459 klassOop Dependencies::DepStream::spot_check_dependency_at(DepChange& changes) { 1460 if (!changes.involves_context(context_type())) 1461 // irrelevant dependency; skip it 1462 return NULL; 1463 1464 return check_dependency_impl(&changes); 1465 } 1466 1467 1468 void DepChange::initialize() { 1469 // entire transaction must be under this lock: 1470 assert_lock_strong(Compile_lock); 1471 1472 // Mark all dependee and all its superclasses 1473 // Mark transitive interfaces 1474 for (ContextStream str(*this); str.next(); ) { 1475 klassOop d = str.klass(); 1476 assert(!instanceKlass::cast(d)->is_marked_dependent(), "checking"); 1477 instanceKlass::cast(d)->set_is_marked_dependent(true); 1478 } 1479 } 1480 1481 DepChange::~DepChange() { 1482 // Unmark all dependee and all its superclasses 1483 // Unmark transitive interfaces 1484 for (ContextStream str(*this); str.next(); ) { 1485 klassOop d = str.klass(); 1486 instanceKlass::cast(d)->set_is_marked_dependent(false); 1487 } 1488 } 1489 1490 bool DepChange::involves_context(klassOop k) { 1491 if (k == NULL || !Klass::cast(k)->oop_is_instance()) { 1492 return false; 1493 } 1494 instanceKlass* ik = instanceKlass::cast(k); 1495 bool is_contained = ik->is_marked_dependent(); 1496 assert(is_contained == Klass::cast(new_type())->is_subtype_of(k), 1497 "correct marking of potential context types"); 1498 return is_contained; 1499 } 1500 1501 bool DepChange::ContextStream::next() { 1502 switch (_change_type) { 1503 case Start_Klass: // initial state; _klass is the new type 1504 _ti_base = instanceKlass::cast(_klass)->transitive_interfaces(); 1505 _ti_index = 0; 1506 _change_type = Change_new_type; 1507 return true; 1508 case Change_new_type: 1509 // fall through: 1510 _change_type = Change_new_sub; 1511 case Change_new_sub: 1512 // 6598190: brackets workaround Sun Studio C++ compiler bug 6629277 1513 { 1514 _klass = instanceKlass::cast(_klass)->super(); 1515 if (_klass != NULL) { 1516 return true; 1517 } 1518 } 1519 // else set up _ti_limit and fall through: 1520 _ti_limit = (_ti_base == NULL) ? 0 : _ti_base->length(); 1521 _change_type = Change_new_impl; 1522 case Change_new_impl: 1523 if (_ti_index < _ti_limit) { 1524 _klass = klassOop( _ti_base->obj_at(_ti_index++) ); 1525 return true; 1526 } 1527 // fall through: 1528 _change_type = NO_CHANGE; // iterator is exhausted 1529 case NO_CHANGE: 1530 break; 1531 default: 1532 ShouldNotReachHere(); 1533 } 1534 return false; 1535 } 1536 1537 void DepChange::print() { 1538 int nsup = 0, nint = 0; 1539 for (ContextStream str(*this); str.next(); ) { 1540 klassOop k = str.klass(); 1541 switch (str.change_type()) { 1542 case Change_new_type: 1543 tty->print_cr(" dependee = %s", instanceKlass::cast(k)->external_name()); 1544 break; 1545 case Change_new_sub: 1546 if (!WizardMode) { 1547 ++nsup; 1548 } else { 1549 tty->print_cr(" context super = %s", instanceKlass::cast(k)->external_name()); 1550 } 1551 break; 1552 case Change_new_impl: 1553 if (!WizardMode) { 1554 ++nint; 1555 } else { 1556 tty->print_cr(" context interface = %s", instanceKlass::cast(k)->external_name()); 1557 } 1558 break; 1559 } 1560 } 1561 if (nsup + nint != 0) { 1562 tty->print_cr(" context supers = %d, interfaces = %d", nsup, nint); 1563 } 1564 } 1565 1566 #ifndef PRODUCT 1567 void Dependencies::print_statistics() { 1568 if (deps_find_witness_print != 0) { 1569 // Call one final time, to flush out the data. 1570 deps_find_witness_print = -1; 1571 count_find_witness_calls(); 1572 } 1573 } 1574 #endif