1 /*
   2  * Copyright (c) 2005, 2025, 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 "ci/ciArrayKlass.hpp"
  26 #include "ci/ciEnv.hpp"
  27 #include "ci/ciKlass.hpp"
  28 #include "ci/ciMethod.hpp"
  29 #include "classfile/javaClasses.inline.hpp"
  30 #include "classfile/vmClasses.hpp"
  31 #include "code/dependencies.hpp"
  32 #include "compiler/compileBroker.hpp"
  33 #include "compiler/compileLog.hpp"
  34 #include "compiler/compileTask.hpp"
  35 #include "memory/resourceArea.hpp"
  36 #include "oops/klass.hpp"
  37 #include "oops/method.inline.hpp"
  38 #include "oops/objArrayKlass.hpp"
  39 #include "oops/oop.inline.hpp"
  40 #include "runtime/flags/flagSetting.hpp"
  41 #include "runtime/handles.inline.hpp"
  42 #include "runtime/javaThread.inline.hpp"
  43 #include "runtime/jniHandles.inline.hpp"
  44 #include "runtime/mutexLocker.hpp"
  45 #include "runtime/perfData.hpp"
  46 #include "runtime/vmThread.hpp"
  47 #include "utilities/copy.hpp"
  48 
  49 
  50 #ifdef ASSERT
  51 static bool must_be_in_vm() {
  52   Thread* thread = Thread::current();
  53   if (thread->is_Java_thread()) {
  54     return JavaThread::cast(thread)->thread_state() == _thread_in_vm;
  55   } else {
  56     return true;  // Could be VMThread or GC thread
  57   }
  58 }
  59 #endif //ASSERT
  60 
  61 bool Dependencies::_verify_in_progress = false;  // don't -Xlog:dependencies
  62 
  63 void Dependencies::initialize(ciEnv* env) {
  64   Arena* arena = env->arena();
  65   _oop_recorder = env->oop_recorder();
  66   _log = env->log();
  67   _dep_seen = new(arena) GrowableArray<int>(arena, 500, 0, 0);
  68 #if INCLUDE_JVMCI
  69   _using_dep_values = false;
  70 #endif
  71   DEBUG_ONLY(_deps[end_marker] = nullptr);
  72   for (int i = (int)FIRST_TYPE; i < (int)TYPE_LIMIT; i++) {
  73     _deps[i] = new(arena) GrowableArray<ciBaseObject*>(arena, 10, 0, nullptr);
  74   }
  75   _content_bytes = nullptr;
  76   _size_in_bytes = (size_t)-1;
  77 
  78   assert(TYPE_LIMIT <= (1<<LG2_TYPE_LIMIT), "sanity");
  79 }
  80 
  81 void Dependencies::assert_evol_method(ciMethod* m) {
  82   assert_common_1(evol_method, m);
  83 }
  84 
  85 void Dependencies::assert_leaf_type(ciKlass* ctxk) {
  86   if (ctxk->is_array_klass()) {
  87     // As a special case, support this assertion on an array type,
  88     // which reduces to an assertion on its element type.
  89     // Note that this cannot be done with assertions that
  90     // relate to concreteness or abstractness.
  91     ciType* elemt = ctxk->as_array_klass()->base_element_type();
  92     if (!elemt->is_instance_klass())  return;   // Ex:  int[][]
  93     ctxk = elemt->as_instance_klass();
  94     //if (ctxk->is_final())  return;            // Ex:  String[][]
  95   }
  96   check_ctxk(ctxk);
  97   assert_common_1(leaf_type, ctxk);
  98 }
  99 
 100 void Dependencies::assert_abstract_with_unique_concrete_subtype(ciKlass* ctxk, ciKlass* conck) {
 101   check_ctxk_abstract(ctxk);
 102   assert_common_2(abstract_with_unique_concrete_subtype, ctxk, conck);
 103 }
 104 
 105 void Dependencies::assert_unique_concrete_method(ciKlass* ctxk, ciMethod* uniqm) {
 106   check_ctxk(ctxk);
 107   check_unique_method(ctxk, uniqm);
 108   assert_common_2(unique_concrete_method_2, ctxk, uniqm);
 109 }
 110 
 111 void Dependencies::assert_unique_concrete_method(ciKlass* ctxk, ciMethod* uniqm, ciKlass* resolved_klass, ciMethod* resolved_method) {
 112   check_ctxk(ctxk);
 113   check_unique_method(ctxk, uniqm);
 114   assert_common_4(unique_concrete_method_4, ctxk, uniqm, resolved_klass, resolved_method);
 115 }
 116 
 117 void Dependencies::assert_unique_implementor(ciInstanceKlass* ctxk, ciInstanceKlass* uniqk) {
 118   check_ctxk(ctxk);
 119   check_unique_implementor(ctxk, uniqk);
 120   assert_common_2(unique_implementor, ctxk, uniqk);
 121 }
 122 
 123 void Dependencies::assert_has_no_finalizable_subclasses(ciKlass* ctxk) {
 124   check_ctxk(ctxk);
 125   assert_common_1(no_finalizable_subclasses, ctxk);
 126 }
 127 
 128 void Dependencies::assert_call_site_target_value(ciCallSite* call_site, ciMethodHandle* method_handle) {
 129   assert_common_2(call_site_target_value, call_site, method_handle);
 130 }
 131 
 132 #if INCLUDE_JVMCI
 133 
 134 Dependencies::Dependencies(Arena* arena, OopRecorder* oop_recorder, CompileLog* log) {
 135   _oop_recorder = oop_recorder;
 136   _log = log;
 137   _dep_seen = new(arena) GrowableArray<int>(arena, 500, 0, 0);
 138   _using_dep_values = true;
 139   DEBUG_ONLY(_dep_values[end_marker] = nullptr);
 140   for (int i = (int)FIRST_TYPE; i < (int)TYPE_LIMIT; i++) {
 141     _dep_values[i] = new(arena) GrowableArray<DepValue>(arena, 10, 0, DepValue());
 142   }
 143   _content_bytes = nullptr;
 144   _size_in_bytes = (size_t)-1;
 145 
 146   assert(TYPE_LIMIT <= (1<<LG2_TYPE_LIMIT), "sanity");
 147 }
 148 
 149 void Dependencies::assert_evol_method(Method* m) {
 150   assert_common_1(evol_method, DepValue(_oop_recorder, m));
 151 }
 152 
 153 void Dependencies::assert_has_no_finalizable_subclasses(Klass* ctxk) {
 154   check_ctxk(ctxk);
 155   assert_common_1(no_finalizable_subclasses, DepValue(_oop_recorder, ctxk));
 156 }
 157 
 158 void Dependencies::assert_leaf_type(Klass* ctxk) {
 159   if (ctxk->is_array_klass()) {
 160     // As a special case, support this assertion on an array type,
 161     // which reduces to an assertion on its element type.
 162     // Note that this cannot be done with assertions that
 163     // relate to concreteness or abstractness.
 164     BasicType elemt = ArrayKlass::cast(ctxk)->element_type();
 165     if (is_java_primitive(elemt))  return;   // Ex:  int[][]
 166     ctxk = ObjArrayKlass::cast(ctxk)->bottom_klass();
 167     //if (ctxk->is_final())  return;            // Ex:  String[][]
 168   }
 169   check_ctxk(ctxk);
 170   assert_common_1(leaf_type, DepValue(_oop_recorder, ctxk));
 171 }
 172 
 173 void Dependencies::assert_abstract_with_unique_concrete_subtype(Klass* ctxk, Klass* conck) {
 174   check_ctxk_abstract(ctxk);
 175   DepValue ctxk_dv(_oop_recorder, ctxk);
 176   DepValue conck_dv(_oop_recorder, conck, &ctxk_dv);
 177   assert_common_2(abstract_with_unique_concrete_subtype, ctxk_dv, conck_dv);
 178 }
 179 
 180 void Dependencies::assert_unique_implementor(InstanceKlass* ctxk, InstanceKlass* uniqk) {
 181   check_ctxk(ctxk);
 182   assert(ctxk->is_interface(), "not an interface");
 183   assert(ctxk->implementor() == uniqk, "not a unique implementor");
 184   assert_common_2(unique_implementor, DepValue(_oop_recorder, ctxk), DepValue(_oop_recorder, uniqk));
 185 }
 186 
 187 void Dependencies::assert_unique_concrete_method(Klass* ctxk, Method* uniqm) {
 188   check_ctxk(ctxk);
 189   check_unique_method(ctxk, uniqm);
 190   assert_common_2(unique_concrete_method_2, DepValue(_oop_recorder, ctxk), DepValue(_oop_recorder, uniqm));
 191 }
 192 
 193 void Dependencies::assert_call_site_target_value(oop call_site, oop method_handle) {
 194   assert_common_2(call_site_target_value, DepValue(_oop_recorder, JNIHandles::make_local(call_site)), DepValue(_oop_recorder, JNIHandles::make_local(method_handle)));
 195 }
 196 
 197 #endif // INCLUDE_JVMCI
 198 
 199 
 200 // Helper function.  If we are adding a new dep. under ctxk2,
 201 // try to find an old dep. under a broader* ctxk1.  If there is
 202 //
 203 bool Dependencies::maybe_merge_ctxk(GrowableArray<ciBaseObject*>* deps,
 204                                     int ctxk_i, ciKlass* ctxk2) {
 205   ciKlass* ctxk1 = deps->at(ctxk_i)->as_metadata()->as_klass();
 206   if (ctxk2->is_subtype_of(ctxk1)) {
 207     return true;  // success, and no need to change
 208   } else if (ctxk1->is_subtype_of(ctxk2)) {
 209     // new context class fully subsumes previous one
 210     deps->at_put(ctxk_i, ctxk2);
 211     return true;
 212   } else {
 213     return false;
 214   }
 215 }
 216 
 217 void Dependencies::assert_common_1(DepType dept, ciBaseObject* x) {
 218   assert(dep_args(dept) == 1, "sanity");
 219   log_dependency(dept, x);
 220   GrowableArray<ciBaseObject*>* deps = _deps[dept];
 221 
 222   // see if the same (or a similar) dep is already recorded
 223   if (note_dep_seen(dept, x)) {
 224     assert(deps->find(x) >= 0, "sanity");
 225   } else {
 226     deps->append(x);
 227   }
 228 }
 229 
 230 void Dependencies::assert_common_2(DepType dept,
 231                                    ciBaseObject* x0, ciBaseObject* x1) {
 232   assert(dep_args(dept) == 2, "sanity");
 233   log_dependency(dept, x0, x1);
 234   GrowableArray<ciBaseObject*>* deps = _deps[dept];
 235 
 236   // see if the same (or a similar) dep is already recorded
 237   bool has_ctxk = has_explicit_context_arg(dept);
 238   if (has_ctxk) {
 239     assert(dep_context_arg(dept) == 0, "sanity");
 240     if (note_dep_seen(dept, x1)) {
 241       // look in this bucket for redundant assertions
 242       const int stride = 2;
 243       for (int i = deps->length(); (i -= stride) >= 0; ) {
 244         ciBaseObject* y1 = deps->at(i+1);
 245         if (x1 == y1) {  // same subject; check the context
 246           if (maybe_merge_ctxk(deps, i+0, x0->as_metadata()->as_klass())) {
 247             return;
 248           }
 249         }
 250       }
 251     }
 252   } else {
 253     bool dep_seen_x0 = note_dep_seen(dept, x0); // records x0 for future queries
 254     bool dep_seen_x1 = note_dep_seen(dept, x1); // records x1 for future queries
 255     if (dep_seen_x0 && dep_seen_x1) {
 256       // look in this bucket for redundant assertions
 257       const int stride = 2;
 258       for (int i = deps->length(); (i -= stride) >= 0; ) {
 259         ciBaseObject* y0 = deps->at(i+0);
 260         ciBaseObject* y1 = deps->at(i+1);
 261         if (x0 == y0 && x1 == y1) {
 262           return;
 263         }
 264       }
 265     }
 266   }
 267 
 268   // append the assertion in the correct bucket:
 269   deps->append(x0);
 270   deps->append(x1);
 271 }
 272 
 273 void Dependencies::assert_common_4(DepType dept,
 274                                    ciKlass* ctxk, ciBaseObject* x1, ciBaseObject* x2, ciBaseObject* x3) {
 275   assert(has_explicit_context_arg(dept), "sanity");
 276   assert(dep_context_arg(dept) == 0, "sanity");
 277   assert(dep_args(dept) == 4, "sanity");
 278   log_dependency(dept, ctxk, x1, x2, x3);
 279   GrowableArray<ciBaseObject*>* deps = _deps[dept];
 280 
 281   // see if the same (or a similar) dep is already recorded
 282   bool dep_seen_x1 = note_dep_seen(dept, x1); // records x1 for future queries
 283   bool dep_seen_x2 = note_dep_seen(dept, x2); // records x2 for future queries
 284   bool dep_seen_x3 = note_dep_seen(dept, x3); // records x3 for future queries
 285   if (dep_seen_x1 && dep_seen_x2 && dep_seen_x3) {
 286     // look in this bucket for redundant assertions
 287     const int stride = 4;
 288     for (int i = deps->length(); (i -= stride) >= 0; ) {
 289       ciBaseObject* y1 = deps->at(i+1);
 290       ciBaseObject* y2 = deps->at(i+2);
 291       ciBaseObject* y3 = deps->at(i+3);
 292       if (x1 == y1 && x2 == y2 && x3 == y3) {  // same subjects; check the context
 293         if (maybe_merge_ctxk(deps, i+0, ctxk)) {
 294           return;
 295         }
 296       }
 297     }
 298   }
 299   // append the assertion in the correct bucket:
 300   deps->append(ctxk);
 301   deps->append(x1);
 302   deps->append(x2);
 303   deps->append(x3);
 304 }
 305 
 306 #if INCLUDE_JVMCI
 307 bool Dependencies::maybe_merge_ctxk(GrowableArray<DepValue>* deps,
 308                                     int ctxk_i, DepValue ctxk2_dv) {
 309   Klass* ctxk1 = deps->at(ctxk_i).as_klass(_oop_recorder);
 310   Klass* ctxk2 = ctxk2_dv.as_klass(_oop_recorder);
 311   if (ctxk2->is_subtype_of(ctxk1)) {
 312     return true;  // success, and no need to change
 313   } else if (ctxk1->is_subtype_of(ctxk2)) {
 314     // new context class fully subsumes previous one
 315     deps->at_put(ctxk_i, ctxk2_dv);
 316     return true;
 317   } else {
 318     return false;
 319   }
 320 }
 321 
 322 void Dependencies::assert_common_1(DepType dept, DepValue x) {
 323   assert(dep_args(dept) == 1, "sanity");
 324   //log_dependency(dept, x);
 325   GrowableArray<DepValue>* deps = _dep_values[dept];
 326 
 327   // see if the same (or a similar) dep is already recorded
 328   if (note_dep_seen(dept, x)) {
 329     assert(deps->find(x) >= 0, "sanity");
 330   } else {
 331     deps->append(x);
 332   }
 333 }
 334 
 335 void Dependencies::assert_common_2(DepType dept,
 336                                    DepValue x0, DepValue x1) {
 337   assert(dep_args(dept) == 2, "sanity");
 338   //log_dependency(dept, x0, x1);
 339   GrowableArray<DepValue>* deps = _dep_values[dept];
 340 
 341   // see if the same (or a similar) dep is already recorded
 342   bool has_ctxk = has_explicit_context_arg(dept);
 343   if (has_ctxk) {
 344     assert(dep_context_arg(dept) == 0, "sanity");
 345     if (note_dep_seen(dept, x1)) {
 346       // look in this bucket for redundant assertions
 347       const int stride = 2;
 348       for (int i = deps->length(); (i -= stride) >= 0; ) {
 349         DepValue y1 = deps->at(i+1);
 350         if (x1 == y1) {  // same subject; check the context
 351           if (maybe_merge_ctxk(deps, i+0, x0)) {
 352             return;
 353           }
 354         }
 355       }
 356     }
 357   } else {
 358     bool dep_seen_x0 = note_dep_seen(dept, x0); // records x0 for future queries
 359     bool dep_seen_x1 = note_dep_seen(dept, x1); // records x1 for future queries
 360     if (dep_seen_x0 && dep_seen_x1) {
 361       // look in this bucket for redundant assertions
 362       const int stride = 2;
 363       for (int i = deps->length(); (i -= stride) >= 0; ) {
 364         DepValue y0 = deps->at(i+0);
 365         DepValue y1 = deps->at(i+1);
 366         if (x0 == y0 && x1 == y1) {
 367           return;
 368         }
 369       }
 370     }
 371   }
 372 
 373   // append the assertion in the correct bucket:
 374   deps->append(x0);
 375   deps->append(x1);
 376 }
 377 #endif // INCLUDE_JVMCI
 378 
 379 /// Support for encoding dependencies into an nmethod:
 380 
 381 void Dependencies::copy_to(nmethod* nm) {
 382   address beg = nm->dependencies_begin();
 383   address end = nm->dependencies_end();
 384   guarantee(end - beg >= (ptrdiff_t) size_in_bytes(), "bad sizing");
 385   (void)memcpy(beg, content_bytes(), size_in_bytes());
 386   assert(size_in_bytes() % sizeof(HeapWord) == 0, "copy by words");
 387 }
 388 
 389 static int sort_dep(ciBaseObject** p1, ciBaseObject** p2, int narg) {
 390   for (int i = 0; i < narg; i++) {
 391     int diff = p1[i]->ident() - p2[i]->ident();
 392     if (diff != 0)  return diff;
 393   }
 394   return 0;
 395 }
 396 static int sort_dep_arg_1(ciBaseObject** p1, ciBaseObject** p2)
 397 { return sort_dep(p1, p2, 1); }
 398 static int sort_dep_arg_2(ciBaseObject** p1, ciBaseObject** p2)
 399 { return sort_dep(p1, p2, 2); }
 400 static int sort_dep_arg_3(ciBaseObject** p1, ciBaseObject** p2)
 401 { return sort_dep(p1, p2, 3); }
 402 static int sort_dep_arg_4(ciBaseObject** p1, ciBaseObject** p2)
 403 { return sort_dep(p1, p2, 4); }
 404 
 405 #if INCLUDE_JVMCI
 406 // metadata deps are sorted before object deps
 407 static int sort_dep_value(Dependencies::DepValue* p1, Dependencies::DepValue* p2, int narg) {
 408   for (int i = 0; i < narg; i++) {
 409     int diff = p1[i].sort_key() - p2[i].sort_key();
 410     if (diff != 0)  return diff;
 411   }
 412   return 0;
 413 }
 414 static int sort_dep_value_arg_1(Dependencies::DepValue* p1, Dependencies::DepValue* p2)
 415 { return sort_dep_value(p1, p2, 1); }
 416 static int sort_dep_value_arg_2(Dependencies::DepValue* p1, Dependencies::DepValue* p2)
 417 { return sort_dep_value(p1, p2, 2); }
 418 static int sort_dep_value_arg_3(Dependencies::DepValue* p1, Dependencies::DepValue* p2)
 419 { return sort_dep_value(p1, p2, 3); }
 420 #endif // INCLUDE_JVMCI
 421 
 422 void Dependencies::sort_all_deps() {
 423 #if INCLUDE_JVMCI
 424   if (_using_dep_values) {
 425     for (int deptv = (int)FIRST_TYPE; deptv < (int)TYPE_LIMIT; deptv++) {
 426       DepType dept = (DepType)deptv;
 427       GrowableArray<DepValue>* deps = _dep_values[dept];
 428       if (deps->length() <= 1)  continue;
 429       switch (dep_args(dept)) {
 430       case 1: deps->sort(sort_dep_value_arg_1, 1); break;
 431       case 2: deps->sort(sort_dep_value_arg_2, 2); break;
 432       case 3: deps->sort(sort_dep_value_arg_3, 3); break;
 433       default: ShouldNotReachHere(); break;
 434       }
 435     }
 436     return;
 437   }
 438 #endif // INCLUDE_JVMCI
 439   for (int deptv = (int)FIRST_TYPE; deptv < (int)TYPE_LIMIT; deptv++) {
 440     DepType dept = (DepType)deptv;
 441     GrowableArray<ciBaseObject*>* deps = _deps[dept];
 442     if (deps->length() <= 1)  continue;
 443     switch (dep_args(dept)) {
 444     case 1: deps->sort(sort_dep_arg_1, 1); break;
 445     case 2: deps->sort(sort_dep_arg_2, 2); break;
 446     case 3: deps->sort(sort_dep_arg_3, 3); break;
 447     case 4: deps->sort(sort_dep_arg_4, 4); break;
 448     default: ShouldNotReachHere(); break;
 449     }
 450   }
 451 }
 452 
 453 size_t Dependencies::estimate_size_in_bytes() {
 454   size_t est_size = 100;
 455 #if INCLUDE_JVMCI
 456   if (_using_dep_values) {
 457     for (int deptv = (int)FIRST_TYPE; deptv < (int)TYPE_LIMIT; deptv++) {
 458       DepType dept = (DepType)deptv;
 459       GrowableArray<DepValue>* deps = _dep_values[dept];
 460       est_size += deps->length() * 2;  // tags and argument(s)
 461     }
 462     return est_size;
 463   }
 464 #endif // INCLUDE_JVMCI
 465   for (int deptv = (int)FIRST_TYPE; deptv < (int)TYPE_LIMIT; deptv++) {
 466     DepType dept = (DepType)deptv;
 467     GrowableArray<ciBaseObject*>* deps = _deps[dept];
 468     est_size += deps->length()*2;  // tags and argument(s)
 469   }
 470   return est_size;
 471 }
 472 
 473 ciKlass* Dependencies::ctxk_encoded_as_null(DepType dept, ciBaseObject* x) {
 474   switch (dept) {
 475   case unique_concrete_method_2:
 476   case unique_concrete_method_4:
 477     return x->as_metadata()->as_method()->holder();
 478   default:
 479     return nullptr;  // let nullptr be nullptr
 480   }
 481 }
 482 
 483 Klass* Dependencies::ctxk_encoded_as_null(DepType dept, Metadata* x) {
 484   assert(must_be_in_vm(), "raw oops here");
 485   switch (dept) {
 486   case unique_concrete_method_2:
 487   case unique_concrete_method_4:
 488     assert(x->is_method(), "sanity");
 489     return ((Method*)x)->method_holder();
 490   default:
 491     return nullptr;  // let nullptr be nullptr
 492   }
 493 }
 494 
 495 void Dependencies::encode_content_bytes() {
 496   sort_all_deps();
 497 
 498   // cast is safe, no deps can overflow INT_MAX
 499   CompressedWriteStream bytes((int)estimate_size_in_bytes());
 500 
 501 #if INCLUDE_JVMCI
 502   if (_using_dep_values) {
 503     for (int deptv = (int)FIRST_TYPE; deptv < (int)TYPE_LIMIT; deptv++) {
 504       DepType dept = (DepType)deptv;
 505       GrowableArray<DepValue>* deps = _dep_values[dept];
 506       if (deps->length() == 0)  continue;
 507       int stride = dep_args(dept);
 508       int ctxkj  = dep_context_arg(dept);  // -1 if no context arg
 509       assert(stride > 0, "sanity");
 510       for (int i = 0; i < deps->length(); i += stride) {
 511         jbyte code_byte = (jbyte)dept;
 512         int skipj = -1;
 513         if (ctxkj >= 0 && ctxkj+1 < stride) {
 514           Klass*  ctxk = deps->at(i+ctxkj+0).as_klass(_oop_recorder);
 515           DepValue x = deps->at(i+ctxkj+1);  // following argument
 516           if (ctxk == ctxk_encoded_as_null(dept, x.as_metadata(_oop_recorder))) {
 517             skipj = ctxkj;  // we win:  maybe one less oop to keep track of
 518             code_byte |= default_context_type_bit;
 519           }
 520         }
 521         bytes.write_byte(code_byte);
 522         for (int j = 0; j < stride; j++) {
 523           if (j == skipj)  continue;
 524           DepValue v = deps->at(i+j);
 525           int idx = v.index();
 526           bytes.write_int(idx);
 527         }
 528       }
 529     }
 530   } else {
 531 #endif // INCLUDE_JVMCI
 532   for (int deptv = (int)FIRST_TYPE; deptv < (int)TYPE_LIMIT; deptv++) {
 533     DepType dept = (DepType)deptv;
 534     GrowableArray<ciBaseObject*>* deps = _deps[dept];
 535     if (deps->length() == 0)  continue;
 536     int stride = dep_args(dept);
 537     int ctxkj  = dep_context_arg(dept);  // -1 if no context arg
 538     assert(stride > 0, "sanity");
 539     for (int i = 0; i < deps->length(); i += stride) {
 540       jbyte code_byte = (jbyte)dept;
 541       int skipj = -1;
 542       if (ctxkj >= 0 && ctxkj+1 < stride) {
 543         ciKlass*  ctxk = deps->at(i+ctxkj+0)->as_metadata()->as_klass();
 544         ciBaseObject* x     = deps->at(i+ctxkj+1);  // following argument
 545         if (ctxk == ctxk_encoded_as_null(dept, x)) {
 546           skipj = ctxkj;  // we win:  maybe one less oop to keep track of
 547           code_byte |= default_context_type_bit;
 548         }
 549       }
 550       bytes.write_byte(code_byte);
 551       for (int j = 0; j < stride; j++) {
 552         if (j == skipj)  continue;
 553         ciBaseObject* v = deps->at(i+j);
 554         int idx;
 555         if (v->is_object()) {
 556           idx = _oop_recorder->find_index(v->as_object()->constant_encoding());
 557         } else {
 558           ciMetadata* meta = v->as_metadata();
 559           idx = _oop_recorder->find_index(meta->constant_encoding());
 560         }
 561         bytes.write_int(idx);
 562       }
 563     }
 564   }
 565 #if INCLUDE_JVMCI
 566   }
 567 #endif
 568 
 569   // write a sentinel byte to mark the end
 570   bytes.write_byte(end_marker);
 571 
 572   // round it out to a word boundary
 573   while (bytes.position() % sizeof(HeapWord) != 0) {
 574     bytes.write_byte(end_marker);
 575   }
 576 
 577   // check whether the dept byte encoding really works
 578   assert((jbyte)default_context_type_bit != 0, "byte overflow");
 579 
 580   _content_bytes = bytes.buffer();
 581   _size_in_bytes = bytes.position();
 582 }
 583 
 584 
 585 const char* Dependencies::_dep_name[TYPE_LIMIT] = {
 586   "end_marker",
 587   "evol_method",
 588   "leaf_type",
 589   "abstract_with_unique_concrete_subtype",
 590   "unique_concrete_method_2",
 591   "unique_concrete_method_4",
 592   "unique_implementor",
 593   "no_finalizable_subclasses",
 594   "call_site_target_value"
 595 };
 596 
 597 int Dependencies::_dep_args[TYPE_LIMIT] = {
 598   -1,// end_marker
 599   1, // evol_method m
 600   1, // leaf_type ctxk
 601   2, // abstract_with_unique_concrete_subtype ctxk, k
 602   2, // unique_concrete_method_2 ctxk, m
 603   4, // unique_concrete_method_4 ctxk, m, resolved_klass, resolved_method
 604   2, // unique_implementor ctxk, implementor
 605   1, // no_finalizable_subclasses ctxk
 606   2  // call_site_target_value call_site, method_handle
 607 };
 608 
 609 const char* Dependencies::dep_name(Dependencies::DepType dept) {
 610   if (!dept_in_mask(dept, all_types))  return "?bad-dep?";
 611   return _dep_name[dept];
 612 }
 613 
 614 int Dependencies::dep_args(Dependencies::DepType dept) {
 615   if (!dept_in_mask(dept, all_types))  return -1;
 616   return _dep_args[dept];
 617 }
 618 
 619 void Dependencies::check_valid_dependency_type(DepType dept) {
 620   guarantee(FIRST_TYPE <= dept && dept < TYPE_LIMIT, "invalid dependency type: %d", (int) dept);
 621 }
 622 
 623 Dependencies::DepType Dependencies::validate_dependencies(CompileTask* task, char** failure_detail) {
 624   int klass_violations = 0;
 625   DepType result = end_marker;
 626   for (Dependencies::DepStream deps(this); deps.next(); ) {
 627     Klass* witness = deps.check_dependency();
 628     if (witness != nullptr) {
 629       if (klass_violations == 0) {
 630         result = deps.type();
 631         if (failure_detail != nullptr && klass_violations == 0) {
 632           // Use a fixed size buffer to prevent the string stream from
 633           // resizing in the context of an inner resource mark.
 634           char* buffer = NEW_RESOURCE_ARRAY(char, O_BUFLEN);
 635           stringStream st(buffer, O_BUFLEN);
 636           deps.print_dependency(&st, witness, true);
 637           *failure_detail = st.as_string();
 638         }
 639       }
 640       klass_violations++;
 641       if (xtty == nullptr) {
 642         // If we're not logging then a single violation is sufficient,
 643         // otherwise we want to log all the dependences which were
 644         // violated.
 645         break;
 646       }
 647     }
 648   }
 649 
 650   return result;
 651 }
 652 
 653 // for the sake of the compiler log, print out current dependencies:
 654 void Dependencies::log_all_dependencies() {
 655   if (log() == nullptr)  return;
 656   ResourceMark rm;
 657   for (int deptv = (int)FIRST_TYPE; deptv < (int)TYPE_LIMIT; deptv++) {
 658     DepType dept = (DepType)deptv;
 659     GrowableArray<ciBaseObject*>* deps = _deps[dept];
 660     int deplen = deps->length();
 661     if (deplen == 0) {
 662       continue;
 663     }
 664     int stride = dep_args(dept);
 665     GrowableArray<ciBaseObject*>* ciargs = new GrowableArray<ciBaseObject*>(stride);
 666     for (int i = 0; i < deps->length(); i += stride) {
 667       for (int j = 0; j < stride; j++) {
 668         // flush out the identities before printing
 669         ciargs->push(deps->at(i+j));
 670       }
 671       write_dependency_to(log(), dept, ciargs);
 672       ciargs->clear();
 673     }
 674     guarantee(deplen == deps->length(), "deps array cannot grow inside nested ResoureMark scope");
 675   }
 676 }
 677 
 678 void Dependencies::write_dependency_to(CompileLog* log,
 679                                        DepType dept,
 680                                        GrowableArray<DepArgument>* args,
 681                                        Klass* witness) {
 682   if (log == nullptr) {
 683     return;
 684   }
 685   ResourceMark rm;
 686   ciEnv* env = ciEnv::current();
 687   GrowableArray<ciBaseObject*>* ciargs = new GrowableArray<ciBaseObject*>(args->length());
 688   for (GrowableArrayIterator<DepArgument> it = args->begin(); it != args->end(); ++it) {
 689     DepArgument arg = *it;
 690     if (arg.is_oop()) {
 691       ciargs->push(env->get_object(arg.oop_value()));
 692     } else {
 693       ciargs->push(env->get_metadata(arg.metadata_value()));
 694     }
 695   }
 696   int argslen = ciargs->length();
 697   Dependencies::write_dependency_to(log, dept, ciargs, witness);
 698   guarantee(argslen == ciargs->length(), "ciargs array cannot grow inside nested ResoureMark scope");
 699 }
 700 
 701 void Dependencies::write_dependency_to(CompileLog* log,
 702                                        DepType dept,
 703                                        GrowableArray<ciBaseObject*>* args,
 704                                        Klass* witness) {
 705   if (log == nullptr) {
 706     return;
 707   }
 708   ResourceMark rm;
 709   GrowableArray<int>* argids = new GrowableArray<int>(args->length());
 710   for (GrowableArrayIterator<ciBaseObject*> it = args->begin(); it != args->end(); ++it) {
 711     ciBaseObject* obj = *it;
 712     if (obj->is_object()) {
 713       argids->push(log->identify(obj->as_object()));
 714     } else {
 715       argids->push(log->identify(obj->as_metadata()));
 716     }
 717   }
 718   if (witness != nullptr) {
 719     log->begin_elem("dependency_failed");
 720   } else {
 721     log->begin_elem("dependency");
 722   }
 723   log->print(" type='%s'", dep_name(dept));
 724   const int ctxkj = dep_context_arg(dept);  // -1 if no context arg
 725   if (ctxkj >= 0 && ctxkj < argids->length()) {
 726     log->print(" ctxk='%d'", argids->at(ctxkj));
 727   }
 728   // write remaining arguments, if any.
 729   for (int j = 0; j < argids->length(); j++) {
 730     if (j == ctxkj)  continue;  // already logged
 731     if (j == 1) {
 732       log->print(  " x='%d'",    argids->at(j));
 733     } else {
 734       log->print(" x%d='%d'", j, argids->at(j));
 735     }
 736   }
 737   if (witness != nullptr) {
 738     log->object("witness", witness);
 739     log->stamp();
 740   }
 741   log->end_elem();
 742 }
 743 
 744 void Dependencies::write_dependency_to(xmlStream* xtty,
 745                                        DepType dept,
 746                                        GrowableArray<DepArgument>* args,
 747                                        Klass* witness) {
 748   if (xtty == nullptr) {
 749     return;
 750   }
 751   Thread* thread = Thread::current();
 752   HandleMark rm(thread);
 753   ttyLocker ttyl;
 754   int ctxkj = dep_context_arg(dept);  // -1 if no context arg
 755   if (witness != nullptr) {
 756     xtty->begin_elem("dependency_failed");
 757   } else {
 758     xtty->begin_elem("dependency");
 759   }
 760   xtty->print(" type='%s'", dep_name(dept));
 761   if (ctxkj >= 0) {
 762     xtty->object("ctxk", args->at(ctxkj).metadata_value());
 763   }
 764   // write remaining arguments, if any.
 765   for (int j = 0; j < args->length(); j++) {
 766     if (j == ctxkj)  continue;  // already logged
 767     DepArgument arg = args->at(j);
 768     if (j == 1) {
 769       if (arg.is_oop()) {
 770         xtty->object("x", Handle(thread, arg.oop_value()));
 771       } else {
 772         xtty->object("x", arg.metadata_value());
 773       }
 774     } else {
 775       char xn[12];
 776       os::snprintf_checked(xn, sizeof(xn), "x%d", j);
 777       if (arg.is_oop()) {
 778         xtty->object(xn, Handle(thread, arg.oop_value()));
 779       } else {
 780         xtty->object(xn, arg.metadata_value());
 781       }
 782     }
 783   }
 784   if (witness != nullptr) {
 785     xtty->object("witness", witness);
 786     xtty->stamp();
 787   }
 788   xtty->end_elem();
 789 }
 790 
 791 void Dependencies::print_dependency(DepType dept, GrowableArray<DepArgument>* args,
 792                                     Klass* witness, outputStream* st) {
 793   ResourceMark rm;
 794   ttyLocker ttyl;   // keep the following output all in one block
 795   st->print_cr("%s of type %s",
 796                 (witness == nullptr)? "Dependency": "Failed dependency",
 797                 dep_name(dept));
 798   // print arguments
 799   int ctxkj = dep_context_arg(dept);  // -1 if no context arg
 800   for (int j = 0; j < args->length(); j++) {
 801     DepArgument arg = args->at(j);
 802     bool put_star = false;
 803     if (arg.is_null())  continue;
 804     const char* what;
 805     if (j == ctxkj) {
 806       assert(arg.is_metadata(), "must be");
 807       what = "context";
 808       put_star = !Dependencies::is_concrete_klass((Klass*)arg.metadata_value());
 809     } else if (arg.is_method()) {
 810       what = "method ";
 811       put_star = !Dependencies::is_concrete_method((Method*)arg.metadata_value(), nullptr);
 812     } else if (arg.is_klass()) {
 813       what = "class  ";
 814     } else {
 815       what = "object ";
 816     }
 817     st->print("  %s = %s", what, (put_star? "*": ""));
 818     if (arg.is_klass()) {
 819       st->print("%s", ((Klass*)arg.metadata_value())->external_name());
 820     } else if (arg.is_method()) {
 821       ((Method*)arg.metadata_value())->print_value_on(st);
 822     } else if (arg.is_oop()) {
 823       arg.oop_value()->print_value_on(st);
 824     } else {
 825       ShouldNotReachHere(); // Provide impl for this type.
 826     }
 827 
 828     st->cr();
 829   }
 830   if (witness != nullptr) {
 831     bool put_star = !Dependencies::is_concrete_klass(witness);
 832     st->print("  witness = %s%s",
 833               (put_star ? "*": ""),
 834               witness->external_name());
 835     if (witness->is_instance_klass()) {
 836       st->print(" (%s)", InstanceKlass::cast(witness)->init_state_name());
 837     }
 838     st->cr();
 839   }
 840 }
 841 
 842 void Dependencies::DepStream::log_dependency(Klass* witness) {
 843   if (_deps == nullptr && xtty == nullptr)  return;  // fast cutout for runtime
 844   ResourceMark rm;
 845   const int nargs = argument_count();
 846   GrowableArray<DepArgument>* args = new GrowableArray<DepArgument>(nargs);
 847   for (int j = 0; j < nargs; j++) {
 848     if (is_oop_argument(j)) {
 849       args->push(argument_oop(j));
 850     } else {
 851       args->push(argument(j));
 852     }
 853   }
 854   int argslen = args->length();
 855   if (_deps != nullptr && _deps->log() != nullptr) {
 856     if (ciEnv::current() != nullptr) {
 857       Dependencies::write_dependency_to(_deps->log(), type(), args, witness);
 858     } else {
 859       // Treat the CompileLog as an xmlstream instead
 860       Dependencies::write_dependency_to((xmlStream*)_deps->log(), type(), args, witness);
 861     }
 862   } else {
 863     Dependencies::write_dependency_to(xtty, type(), args, witness);
 864   }
 865   guarantee(argslen == args->length(), "args array cannot grow inside nested ResoureMark scope");
 866 }
 867 
 868 void Dependencies::DepStream::print_dependency(outputStream* st, Klass* witness, bool verbose) {
 869   ResourceMark rm;
 870   int nargs = argument_count();
 871   GrowableArray<DepArgument>* args = new GrowableArray<DepArgument>(nargs);
 872   for (int j = 0; j < nargs; j++) {
 873     if (is_oop_argument(j)) {
 874       args->push(argument_oop(j));
 875     } else {
 876       args->push(argument(j));
 877     }
 878   }
 879   int argslen = args->length();
 880   Dependencies::print_dependency(type(), args, witness, st);
 881   if (verbose) {
 882     if (_code != nullptr) {
 883       st->print("  code: ");
 884       _code->print_value_on(st);
 885       st->cr();
 886     }
 887   }
 888   guarantee(argslen == args->length(), "args array cannot grow inside nested ResoureMark scope");
 889 }
 890 
 891 
 892 /// Dependency stream support (decodes dependencies from an nmethod):
 893 
 894 #ifdef ASSERT
 895 void Dependencies::DepStream::initial_asserts(size_t byte_limit) {
 896   assert(must_be_in_vm(), "raw oops here");
 897   _byte_limit = byte_limit;
 898   _type       = undefined_dependency;  // defeat "already at end" assert
 899   assert((_code!=nullptr) + (_deps!=nullptr) == 1, "one or t'other");
 900 }
 901 #endif //ASSERT
 902 
 903 bool Dependencies::DepStream::next() {
 904   assert(_type != end_marker, "already at end");
 905   if (_bytes.position() == 0 && _code != nullptr
 906       && _code->dependencies_size() == 0) {
 907     // Method has no dependencies at all.
 908     return false;
 909   }
 910   int code_byte = (_bytes.read_byte() & 0xFF);
 911   if (code_byte == end_marker) {
 912     DEBUG_ONLY(_type = end_marker);
 913     return false;
 914   } else {
 915     int ctxk_bit = (code_byte & Dependencies::default_context_type_bit);
 916     code_byte -= ctxk_bit;
 917     DepType dept = (DepType)code_byte;
 918     _type = dept;
 919     Dependencies::check_valid_dependency_type(dept);
 920     int stride = _dep_args[dept];
 921     assert(stride == dep_args(dept), "sanity");
 922     int skipj = -1;
 923     if (ctxk_bit != 0) {
 924       skipj = 0;  // currently the only context argument is at zero
 925       assert(skipj == dep_context_arg(dept), "zero arg always ctxk");
 926     }
 927     for (int j = 0; j < stride; j++) {
 928       _xi[j] = (j == skipj)? 0: _bytes.read_int();
 929     }
 930     DEBUG_ONLY(_xi[stride] = -1);   // help detect overruns
 931     return true;
 932   }
 933 }
 934 
 935 inline Metadata* Dependencies::DepStream::recorded_metadata_at(int i) {
 936   Metadata* o = nullptr;
 937   if (_code != nullptr) {
 938     o = _code->metadata_at(i);
 939   } else {
 940     o = _deps->oop_recorder()->metadata_at(i);
 941   }
 942   return o;
 943 }
 944 
 945 inline oop Dependencies::DepStream::recorded_oop_at(int i) {
 946   return (_code != nullptr)
 947          ? _code->oop_at(i)
 948     : JNIHandles::resolve(_deps->oop_recorder()->oop_at(i));
 949 }
 950 
 951 Metadata* Dependencies::DepStream::argument(int i) {
 952   Metadata* result = recorded_metadata_at(argument_index(i));
 953 
 954   if (result == nullptr) { // Explicit context argument can be compressed
 955     int ctxkj = dep_context_arg(type());  // -1 if no explicit context arg
 956     if (ctxkj >= 0 && i == ctxkj && ctxkj+1 < argument_count()) {
 957       result = ctxk_encoded_as_null(type(), argument(ctxkj+1));
 958     }
 959   }
 960 
 961   assert(result == nullptr || result->is_klass() || result->is_method(), "must be");
 962   return result;
 963 }
 964 
 965 /**
 966  * Returns a unique identifier for each dependency argument.
 967  */
 968 uintptr_t Dependencies::DepStream::get_identifier(int i) {
 969   if (is_oop_argument(i)) {
 970     return (uintptr_t)(oopDesc*)argument_oop(i);
 971   } else {
 972     return (uintptr_t)argument(i);
 973   }
 974 }
 975 
 976 oop Dependencies::DepStream::argument_oop(int i) {
 977   oop result = recorded_oop_at(argument_index(i));
 978   assert(oopDesc::is_oop_or_null(result), "must be");
 979   return result;
 980 }
 981 
 982 InstanceKlass* Dependencies::DepStream::context_type() {
 983   assert(must_be_in_vm(), "raw oops here");
 984 
 985   // Most dependencies have an explicit context type argument.
 986   {
 987     int ctxkj = dep_context_arg(type());  // -1 if no explicit context arg
 988     if (ctxkj >= 0) {
 989       Metadata* k = argument(ctxkj);
 990       assert(k != nullptr && k->is_klass(), "type check");
 991       return InstanceKlass::cast((Klass*)k);
 992     }
 993   }
 994 
 995   // Some dependencies are using the klass of the first object
 996   // argument as implicit context type.
 997   {
 998     int ctxkj = dep_implicit_context_arg(type());
 999     if (ctxkj >= 0) {
1000       Klass* k = argument_oop(ctxkj)->klass();
1001       assert(k != nullptr, "type check");
1002       return InstanceKlass::cast(k);
1003     }
1004   }
1005 
1006   // And some dependencies don't have a context type at all,
1007   // e.g. evol_method.
1008   return nullptr;
1009 }
1010 
1011 // ----------------- DependencySignature --------------------------------------
1012 bool DependencySignature::equals(DependencySignature const& s1, DependencySignature const& s2) {
1013   if ((s1.type() != s2.type()) || (s1.args_count() != s2.args_count())) {
1014     return false;
1015   }
1016 
1017   for (int i = 0; i < s1.args_count(); i++) {
1018     if (s1.arg(i) != s2.arg(i)) {
1019       return false;
1020     }
1021   }
1022   return true;
1023 }
1024 
1025 /// Checking dependencies
1026 
1027 // This hierarchy walker inspects subtypes of a given type, trying to find a "bad" class which breaks a dependency.
1028 // Such a class is called a "witness" to the broken dependency.
1029 // While searching around, we ignore "participants", which are already known to the dependency.
1030 class AbstractClassHierarchyWalker {
1031  public:
1032   enum { PARTICIPANT_LIMIT = 3 };
1033 
1034  private:
1035   // if non-zero, tells how many witnesses to convert to participants
1036   uint _record_witnesses;
1037 
1038   // special classes which are not allowed to be witnesses:
1039   Klass* _participants[PARTICIPANT_LIMIT+1];
1040   uint   _num_participants;
1041 
1042 #ifdef ASSERT
1043   uint _nof_requests; // one-shot walker
1044 #endif // ASSERT
1045 
1046   static PerfCounter* _perf_find_witness_anywhere_calls_count;
1047   static PerfCounter* _perf_find_witness_anywhere_steps_count;
1048   static PerfCounter* _perf_find_witness_in_calls_count;
1049 
1050  protected:
1051   virtual Klass* find_witness_in(KlassDepChange& changes) = 0;
1052   virtual Klass* find_witness_anywhere(InstanceKlass* context_type) = 0;
1053 
1054   AbstractClassHierarchyWalker(Klass* participant) : _record_witnesses(0), _num_participants(0)
1055 #ifdef ASSERT
1056   , _nof_requests(0)
1057 #endif // ASSERT
1058   {
1059     for (uint i = 0; i < PARTICIPANT_LIMIT+1; i++) {
1060       _participants[i] = nullptr;
1061     }
1062     if (participant != nullptr) {
1063       add_participant(participant);
1064     }
1065   }
1066 
1067   bool is_participant(Klass* k) {
1068     for (uint i = 0; i < _num_participants; i++) {
1069       if (_participants[i] == k) {
1070         return true;
1071       }
1072     }
1073     return false;
1074   }
1075 
1076   bool record_witness(Klass* witness) {
1077     if (_record_witnesses > 0) {
1078       --_record_witnesses;
1079       add_participant(witness);
1080       return false; // not a witness
1081     } else {
1082       return true; // is a witness
1083     }
1084   }
1085 
1086   class CountingClassHierarchyIterator : public ClassHierarchyIterator {
1087    private:
1088     jlong _nof_steps;
1089    public:
1090     CountingClassHierarchyIterator(InstanceKlass* root) : ClassHierarchyIterator(root), _nof_steps(0) {}
1091 
1092     void next() {
1093       _nof_steps++;
1094       ClassHierarchyIterator::next();
1095     }
1096 
1097     ~CountingClassHierarchyIterator() {
1098       if (UsePerfData) {
1099         _perf_find_witness_anywhere_steps_count->inc(_nof_steps);
1100       }
1101     }
1102   };
1103 
1104  public:
1105   uint num_participants() { return _num_participants; }
1106   Klass* participant(uint n) {
1107     assert(n <= _num_participants, "oob");
1108     if (n < _num_participants) {
1109       return _participants[n];
1110     } else {
1111       return nullptr;
1112     }
1113   }
1114 
1115   void add_participant(Klass* participant) {
1116     assert(!is_participant(participant), "sanity");
1117     assert(_num_participants + _record_witnesses < PARTICIPANT_LIMIT, "oob");
1118     uint np = _num_participants++;
1119     _participants[np] = participant;
1120   }
1121 
1122   void record_witnesses(uint add) {
1123     if (add > PARTICIPANT_LIMIT)  add = PARTICIPANT_LIMIT;
1124     assert(_num_participants + add < PARTICIPANT_LIMIT, "oob");
1125     _record_witnesses = add;
1126   }
1127 
1128   Klass* find_witness(InstanceKlass* context_type, KlassDepChange* changes = nullptr);
1129 
1130   static void init();
1131   static void print_statistics();
1132 };
1133 
1134 PerfCounter* AbstractClassHierarchyWalker::_perf_find_witness_anywhere_calls_count = nullptr;
1135 PerfCounter* AbstractClassHierarchyWalker::_perf_find_witness_anywhere_steps_count = nullptr;
1136 PerfCounter* AbstractClassHierarchyWalker::_perf_find_witness_in_calls_count       = nullptr;
1137 
1138 void AbstractClassHierarchyWalker::init() {
1139   if (UsePerfData) {
1140     EXCEPTION_MARK;
1141     _perf_find_witness_anywhere_calls_count =
1142         PerfDataManager::create_counter(SUN_CI, "findWitnessAnywhere", PerfData::U_Events, CHECK);
1143     _perf_find_witness_anywhere_steps_count =
1144         PerfDataManager::create_counter(SUN_CI, "findWitnessAnywhereSteps", PerfData::U_Events, CHECK);
1145     _perf_find_witness_in_calls_count =
1146         PerfDataManager::create_counter(SUN_CI, "findWitnessIn", PerfData::U_Events, CHECK);
1147   }
1148 }
1149 
1150 Klass* AbstractClassHierarchyWalker::find_witness(InstanceKlass* context_type, KlassDepChange* changes) {
1151   // Current thread must be in VM (not native mode, as in CI):
1152   assert(must_be_in_vm(), "raw oops here");
1153   // Must not move the class hierarchy during this check:
1154   assert_locked_or_safepoint(Compile_lock);
1155   assert(_nof_requests++ == 0, "repeated requests are not supported");
1156 
1157   assert(changes == nullptr || changes->involves_context(context_type), "irrelevant dependency");
1158 
1159   // (Note: Interfaces do not have subclasses.)
1160   // If it is an interface, search its direct implementors.
1161   // (Their subclasses are additional indirect implementors. See InstanceKlass::add_implementor().)
1162   if (context_type->is_interface()) {
1163     int nof_impls = context_type->nof_implementors();
1164     if (nof_impls == 0) {
1165       return nullptr; // no implementors
1166     } else if (nof_impls == 1) { // unique implementor
1167       assert(context_type != context_type->implementor(), "not unique");
1168       context_type = context_type->implementor();
1169     } else { // nof_impls >= 2
1170       // Avoid this case: *I.m > { A.m, C }; B.m > C
1171       // Here, I.m has 2 concrete implementations, but m appears unique
1172       // as A.m, because the search misses B.m when checking C.
1173       // The inherited method B.m was getting missed by the walker
1174       // when interface 'I' was the starting point.
1175       // %%% Until this is fixed more systematically, bail out.
1176       return context_type;
1177     }
1178   }
1179   assert(!context_type->is_interface(), "no interfaces allowed");
1180 
1181   if (changes != nullptr) {
1182     if (UsePerfData) {
1183       _perf_find_witness_in_calls_count->inc();
1184     }
1185     return find_witness_in(*changes);
1186   } else {
1187     if (UsePerfData) {
1188       _perf_find_witness_anywhere_calls_count->inc();
1189     }
1190     return find_witness_anywhere(context_type);
1191   }
1192 }
1193 
1194 class ConcreteSubtypeFinder : public AbstractClassHierarchyWalker {
1195  private:
1196   bool is_witness(Klass* k);
1197 
1198  protected:
1199   virtual Klass* find_witness_in(KlassDepChange& changes);
1200   virtual Klass* find_witness_anywhere(InstanceKlass* context_type);
1201 
1202  public:
1203   ConcreteSubtypeFinder(Klass* participant = nullptr) : AbstractClassHierarchyWalker(participant) {}
1204 };
1205 
1206 bool ConcreteSubtypeFinder::is_witness(Klass* k) {
1207   if (Dependencies::is_concrete_klass(k)) {
1208     return record_witness(k); // concrete subtype
1209   } else {
1210     return false; // not a concrete class
1211   }
1212 }
1213 
1214 Klass* ConcreteSubtypeFinder::find_witness_in(KlassDepChange& changes) {
1215   // When looking for unexpected concrete types, do not look beneath expected ones:
1216   //  * CX > CC > C' is OK, even if C' is new.
1217   //  * CX > { CC,  C' } is not OK if C' is new, and C' is the witness.
1218   Klass* new_type = changes.as_new_klass_change()->new_type();
1219   assert(!is_participant(new_type), "only old classes are participants");
1220   // If the new type is a subtype of a participant, we are done.
1221   for (uint i = 0; i < num_participants(); i++) {
1222     if (changes.involves_context(participant(i))) {
1223       // new guy is protected from this check by previous participant
1224       return nullptr;
1225     }
1226   }
1227   if (is_witness(new_type)) {
1228     return new_type;
1229   }
1230   // No witness found.  The dependency remains unbroken.
1231   return nullptr;
1232 }
1233 
1234 Klass* ConcreteSubtypeFinder::find_witness_anywhere(InstanceKlass* context_type) {
1235   for (CountingClassHierarchyIterator iter(context_type); !iter.done(); iter.next()) {
1236     Klass* sub = iter.klass();
1237     // Do not report participant types.
1238     if (is_participant(sub)) {
1239       // Don't walk beneath a participant since it hides witnesses.
1240       iter.skip_subclasses();
1241     } else if (is_witness(sub)) {
1242       return sub; // found a witness
1243     }
1244   }
1245   // No witness found.  The dependency remains unbroken.
1246   return nullptr;
1247 }
1248 
1249 class ConcreteMethodFinder : public AbstractClassHierarchyWalker {
1250  private:
1251   Symbol* _name;
1252   Symbol* _signature;
1253 
1254   // cache of method lookups
1255   Method* _found_methods[PARTICIPANT_LIMIT+1];
1256 
1257   bool is_witness(Klass* k);
1258 
1259  protected:
1260   virtual Klass* find_witness_in(KlassDepChange& changes);
1261   virtual Klass* find_witness_anywhere(InstanceKlass* context_type);
1262 
1263  public:
1264   bool witnessed_reabstraction_in_supers(Klass* k);
1265 
1266   ConcreteMethodFinder(Method* m, Klass* participant = nullptr) : AbstractClassHierarchyWalker(participant) {
1267     assert(m != nullptr && m->is_method(), "sanity");
1268     _name      = m->name();
1269     _signature = m->signature();
1270 
1271     for (int i = 0; i < PARTICIPANT_LIMIT+1; i++) {
1272       _found_methods[i] = nullptr;
1273     }
1274   }
1275 
1276   // Note:  If n==num_participants, returns nullptr.
1277   Method* found_method(uint n) {
1278     assert(n <= num_participants(), "oob");
1279     Method* fm = _found_methods[n];
1280     assert(n == num_participants() || fm != nullptr, "proper usage");
1281     if (fm != nullptr && fm->method_holder() != participant(n)) {
1282       // Default methods from interfaces can be added to classes. In
1283       // that case the holder of the method is not the class but the
1284       // interface where it's defined.
1285       assert(fm->is_default_method(), "sanity");
1286       return nullptr;
1287     }
1288     return fm;
1289   }
1290 
1291   void add_participant(Klass* participant) {
1292     AbstractClassHierarchyWalker::add_participant(participant);
1293     _found_methods[num_participants()] = nullptr;
1294   }
1295 
1296   bool record_witness(Klass* witness, Method* m) {
1297     _found_methods[num_participants()] = m;
1298     return AbstractClassHierarchyWalker::record_witness(witness);
1299   }
1300 
1301  private:
1302   static PerfCounter* _perf_find_witness_anywhere_calls_count;
1303   static PerfCounter* _perf_find_witness_anywhere_steps_count;
1304   static PerfCounter* _perf_find_witness_in_calls_count;
1305 
1306  public:
1307   static void init();
1308   static void print_statistics();
1309 };
1310 
1311 bool ConcreteMethodFinder::is_witness(Klass* k) {
1312   if (is_participant(k)) {
1313     return false; // do not report participant types
1314   }
1315   if (k->is_instance_klass()) {
1316     InstanceKlass* ik = InstanceKlass::cast(k);
1317     // Search class hierarchy first, skipping private implementations
1318     // as they never override any inherited methods
1319     Method* m = ik->find_instance_method(_name, _signature, Klass::PrivateLookupMode::skip);
1320     if (Dependencies::is_concrete_method(m, ik)) {
1321       return record_witness(k, m); // concrete method found
1322     } else {
1323       // Check for re-abstraction of method
1324       if (!ik->is_interface() && m != nullptr && m->is_abstract()) {
1325         // Found a matching abstract method 'm' in the class hierarchy.
1326         // This is fine iff 'k' is an abstract class and all concrete subtypes
1327         // of 'k' override 'm' and are participates of the current search.
1328         ConcreteSubtypeFinder wf;
1329         for (uint i = 0; i < num_participants(); i++) {
1330           Klass* p = participant(i);
1331           wf.add_participant(p);
1332         }
1333         Klass* w = wf.find_witness(ik);
1334         if (w != nullptr) {
1335           Method* wm = InstanceKlass::cast(w)->find_instance_method(_name, _signature, Klass::PrivateLookupMode::skip);
1336           if (!Dependencies::is_concrete_method(wm, w)) {
1337             // Found a concrete subtype 'w' which does not override abstract method 'm'.
1338             // Bail out because 'm' could be called with 'w' as receiver (leading to an
1339             // AbstractMethodError) and thus the method we are looking for is not unique.
1340             return record_witness(k, m);
1341           }
1342         }
1343       }
1344       // Check interface defaults also, if any exist.
1345       Array<Method*>* default_methods = ik->default_methods();
1346       if (default_methods != nullptr) {
1347         Method* dm = ik->find_method(default_methods, _name, _signature);
1348         if (Dependencies::is_concrete_method(dm, nullptr)) {
1349           return record_witness(k, dm); // default method found
1350         }
1351       }
1352       return false; // no concrete method found
1353     }
1354   } else {
1355     return false; // no methods to find in an array type
1356   }
1357 }
1358 
1359 Klass* ConcreteMethodFinder::find_witness_in(KlassDepChange& changes) {
1360   // When looking for unexpected concrete methods, look beneath expected ones, to see if there are overrides.
1361   //  * CX.m > CC.m > C'.m is not OK, if C'.m is new, and C' is the witness.
1362   Klass* new_type = changes.as_new_klass_change()->new_type();
1363   assert(!is_participant(new_type), "only old classes are participants");
1364   if (is_witness(new_type)) {
1365     return new_type;
1366   } else {
1367     // No witness found, but is_witness() doesn't detect method re-abstraction in case of spot-checking.
1368     if (witnessed_reabstraction_in_supers(new_type)) {
1369       return new_type;
1370     }
1371   }
1372   // No witness found.  The dependency remains unbroken.
1373   return nullptr;
1374 }
1375 
1376 bool ConcreteMethodFinder::witnessed_reabstraction_in_supers(Klass* k) {
1377   if (!k->is_instance_klass()) {
1378     return false; // no methods to find in an array type
1379   } else {
1380     // Looking for a case when an abstract method is inherited into a concrete class.
1381     if (Dependencies::is_concrete_klass(k) && !k->is_interface()) {
1382       Method* m = InstanceKlass::cast(k)->find_instance_method(_name, _signature, Klass::PrivateLookupMode::skip);
1383       if (m != nullptr) {
1384         return false; // no reabstraction possible: local method found
1385       }
1386       for (InstanceKlass* super = k->java_super(); super != nullptr; super = super->java_super()) {
1387         m = super->find_instance_method(_name, _signature, Klass::PrivateLookupMode::skip);
1388         if (m != nullptr) { // inherited method found
1389           if (m->is_abstract() || m->is_overpass()) {
1390             return record_witness(super, m); // abstract method found
1391           }
1392           return false;
1393         }
1394       }
1395       // Miranda.
1396       return true;
1397     }
1398     return false;
1399   }
1400 }
1401 
1402 
1403 Klass* ConcreteMethodFinder::find_witness_anywhere(InstanceKlass* context_type) {
1404   // Walk hierarchy under a context type, looking for unexpected types.
1405   for (CountingClassHierarchyIterator iter(context_type); !iter.done(); iter.next()) {
1406     Klass* sub = iter.klass();
1407     if (is_witness(sub)) {
1408       return sub; // found a witness
1409     }
1410   }
1411   // No witness found.  The dependency remains unbroken.
1412   return nullptr;
1413 }
1414 
1415 // For some method m and some class ctxk (subclass of method holder),
1416 // enumerate all distinct overrides of m in concrete subclasses of ctxk.
1417 // It relies on vtable/itable information to perform method selection on each linked subclass
1418 // and ignores all non yet linked ones (speculatively treat them as "effectively abstract").
1419 class LinkedConcreteMethodFinder : public AbstractClassHierarchyWalker {
1420  private:
1421   InstanceKlass* _resolved_klass;   // resolved class (JVMS-5.4.3.1)
1422   InstanceKlass* _declaring_klass;  // the holder of resolved method (JVMS-5.4.3.3)
1423   int            _vtable_index;     // vtable/itable index of the resolved method
1424   bool           _do_itable_lookup; // choose between itable and vtable lookup logic
1425 
1426   // cache of method lookups
1427   Method* _found_methods[PARTICIPANT_LIMIT+1];
1428 
1429   bool is_witness(Klass* k);
1430   Method* select_method(InstanceKlass* recv_klass);
1431   static int compute_vtable_index(InstanceKlass* resolved_klass, Method* resolved_method, bool& is_itable_index);
1432   static bool is_concrete_klass(InstanceKlass* ik);
1433 
1434   void add_participant(Method* m, Klass* participant) {
1435     uint np = num_participants();
1436     AbstractClassHierarchyWalker::add_participant(participant);
1437     assert(np + 1 == num_participants(), "sanity");
1438     _found_methods[np] = m; // record the method for the participant
1439   }
1440 
1441   bool record_witness(Klass* witness, Method* m) {
1442     for (uint i = 0; i < num_participants(); i++) {
1443       if (found_method(i) == m) {
1444         return false; // already recorded
1445       }
1446     }
1447     // Record not yet seen method.
1448     _found_methods[num_participants()] = m;
1449     return AbstractClassHierarchyWalker::record_witness(witness);
1450   }
1451 
1452   void initialize(Method* participant) {
1453     for (uint i = 0; i < PARTICIPANT_LIMIT+1; i++) {
1454       _found_methods[i] = nullptr;
1455     }
1456     if (participant != nullptr) {
1457       add_participant(participant, participant->method_holder());
1458     }
1459   }
1460 
1461  protected:
1462   virtual Klass* find_witness_in(KlassDepChange& changes);
1463   virtual Klass* find_witness_anywhere(InstanceKlass* context_type);
1464 
1465  public:
1466   // In order to perform method selection, the following info is needed:
1467   //  (1) interface or virtual call;
1468   //  (2) vtable/itable index;
1469   //  (3) declaring class (in case of interface call).
1470   //
1471   // It is prepared based on the results of method resolution: resolved class and resolved method (as specified in JVMS-5.4.3.3).
1472   // Optionally, a method which was previously determined as a unique target (uniqm) is added as a participant
1473   // to enable dependency spot-checking and speed up the search.
1474   LinkedConcreteMethodFinder(InstanceKlass* resolved_klass, Method* resolved_method, Method* uniqm = nullptr) : AbstractClassHierarchyWalker(nullptr) {
1475     assert(resolved_klass->is_linked(), "required");
1476     assert(resolved_method->method_holder()->is_linked(), "required");
1477     assert(!resolved_method->can_be_statically_bound(), "no vtable index available");
1478 
1479     _resolved_klass  = resolved_klass;
1480     _declaring_klass = resolved_method->method_holder();
1481     _vtable_index    = compute_vtable_index(resolved_klass, resolved_method,
1482                                             _do_itable_lookup); // out parameter
1483     assert(_vtable_index >= 0, "invalid vtable index");
1484 
1485     initialize(uniqm);
1486   }
1487 
1488   // Note:  If n==num_participants, returns nullptr.
1489   Method* found_method(uint n) {
1490     assert(n <= num_participants(), "oob");
1491     assert(participant(n) != nullptr || n == num_participants(), "proper usage");
1492     return _found_methods[n];
1493   }
1494 };
1495 
1496 Klass* LinkedConcreteMethodFinder::find_witness_in(KlassDepChange& changes) {
1497   Klass* type = changes.type();
1498 
1499   assert(!is_participant(type), "only old classes are participants");
1500 
1501   if (is_witness(type)) {
1502     return type;
1503   }
1504   return nullptr; // No witness found.  The dependency remains unbroken.
1505 }
1506 
1507 Klass* LinkedConcreteMethodFinder::find_witness_anywhere(InstanceKlass* context_type) {
1508   for (CountingClassHierarchyIterator iter(context_type); !iter.done(); iter.next()) {
1509     Klass* sub = iter.klass();
1510     if (is_witness(sub)) {
1511       return sub;
1512     }
1513     if (sub->is_instance_klass() && !InstanceKlass::cast(sub)->is_linked()) {
1514       iter.skip_subclasses(); // ignore not yet linked classes
1515     }
1516   }
1517   return nullptr; // No witness found. The dependency remains unbroken.
1518 }
1519 
1520 bool LinkedConcreteMethodFinder::is_witness(Klass* k) {
1521   if (is_participant(k)) {
1522     return false; // do not report participant types
1523   } else if (k->is_instance_klass()) {
1524     InstanceKlass* ik = InstanceKlass::cast(k);
1525     if (is_concrete_klass(ik)) {
1526       Method* m = select_method(ik);
1527       return record_witness(ik, m);
1528     } else {
1529       return false; // ignore non-concrete holder class
1530     }
1531   } else {
1532     return false; // no methods to find in an array type
1533   }
1534 }
1535 
1536 Method* LinkedConcreteMethodFinder::select_method(InstanceKlass* recv_klass) {
1537   Method* selected_method = nullptr;
1538   if (_do_itable_lookup) {
1539     assert(_declaring_klass->is_interface(), "sanity");
1540     bool implements_interface; // initialized by method_at_itable_or_null()
1541     selected_method = recv_klass->method_at_itable_or_null(_declaring_klass, _vtable_index,
1542                                                            implements_interface); // out parameter
1543     assert(implements_interface, "not implemented");
1544   } else {
1545     selected_method = recv_klass->method_at_vtable(_vtable_index);
1546   }
1547   return selected_method; // nullptr when corresponding slot is empty (AbstractMethodError case)
1548 }
1549 
1550 int LinkedConcreteMethodFinder::compute_vtable_index(InstanceKlass* resolved_klass, Method* resolved_method,
1551                                                      // out parameter
1552                                                      bool& is_itable_index) {
1553   if (resolved_klass->is_interface() && resolved_method->has_itable_index()) {
1554     is_itable_index = true;
1555     return resolved_method->itable_index();
1556   }
1557   // Check for default or miranda method first.
1558   InstanceKlass* declaring_klass = resolved_method->method_holder();
1559   if (!resolved_klass->is_interface() && declaring_klass->is_interface()) {
1560     is_itable_index = false;
1561     return resolved_klass->vtable_index_of_interface_method(resolved_method);
1562   }
1563   // At this point we are sure that resolved_method is virtual and not
1564   // a default or miranda method; therefore, it must have a valid vtable index.
1565   assert(resolved_method->has_vtable_index(), "");
1566   is_itable_index = false;
1567   return resolved_method->vtable_index();
1568 }
1569 
1570 bool LinkedConcreteMethodFinder::is_concrete_klass(InstanceKlass* ik) {
1571   if (!Dependencies::is_concrete_klass(ik)) {
1572     return false; // not concrete
1573   }
1574   if (ik->is_interface()) {
1575     return false; // interfaces aren't concrete
1576   }
1577   if (!ik->is_linked()) {
1578     return false; // not yet linked classes don't have instances
1579   }
1580   return true;
1581 }
1582 
1583 #ifdef ASSERT
1584 // Assert that m is inherited into ctxk, without intervening overrides.
1585 // (May return true even if this is not true, in corner cases where we punt.)
1586 bool Dependencies::verify_method_context(InstanceKlass* ctxk, Method* m) {
1587   if (m->is_private()) {
1588     return false; // Quick lose.  Should not happen.
1589   }
1590   if (m->method_holder() == ctxk) {
1591     return true;  // Quick win.
1592   }
1593   if (!(m->is_public() || m->is_protected())) {
1594     // The override story is complex when packages get involved.
1595     return true;  // Must punt the assertion to true.
1596   }
1597   Method* lm = ctxk->lookup_method(m->name(), m->signature());
1598   if (lm == nullptr) {
1599     // It might be an interface method
1600     lm = ctxk->lookup_method_in_ordered_interfaces(m->name(), m->signature());
1601   }
1602   if (lm == m) {
1603     // Method m is inherited into ctxk.
1604     return true;
1605   }
1606   if (lm != nullptr) {
1607     if (!(lm->is_public() || lm->is_protected())) {
1608       // Method is [package-]private, so the override story is complex.
1609       return true;  // Must punt the assertion to true.
1610     }
1611     if (lm->is_static()) {
1612       // Static methods don't override non-static so punt
1613       return true;
1614     }
1615     if (!Dependencies::is_concrete_method(lm, ctxk) &&
1616         !Dependencies::is_concrete_method(m, ctxk)) {
1617       // They are both non-concrete
1618       if (lm->method_holder()->is_subtype_of(m->method_holder())) {
1619         // Method m is overridden by lm, but both are non-concrete.
1620         return true;
1621       }
1622       if (lm->method_holder()->is_interface() && m->method_holder()->is_interface() &&
1623           ctxk->is_subtype_of(m->method_holder()) && ctxk->is_subtype_of(lm->method_holder())) {
1624         // Interface method defined in multiple super interfaces
1625         return true;
1626       }
1627     }
1628   }
1629   ResourceMark rm;
1630   tty->print_cr("Dependency method not found in the associated context:");
1631   tty->print_cr("  context = %s", ctxk->external_name());
1632   tty->print(   "  method = "); m->print_short_name(tty); tty->cr();
1633   if (lm != nullptr) {
1634     tty->print( "  found = "); lm->print_short_name(tty); tty->cr();
1635   }
1636   return false;
1637 }
1638 #endif // ASSERT
1639 
1640 bool Dependencies::is_concrete_klass(Klass* k) {
1641   if (k->is_abstract())  return false;
1642   // %%% We could treat classes which are concrete but
1643   // have not yet been instantiated as virtually abstract.
1644   // This would require a deoptimization barrier on first instantiation.
1645   //if (k->is_not_instantiated())  return false;
1646   return true;
1647 }
1648 
1649 bool Dependencies::is_concrete_method(Method* m, Klass* k) {
1650   // nullptr is not a concrete method.
1651   if (m == nullptr) {
1652     return false;
1653   }
1654   // Statics are irrelevant to virtual call sites.
1655   if (m->is_static()) {
1656     return false;
1657   }
1658   // Abstract methods are not concrete.
1659   if (m->is_abstract()) {
1660     return false;
1661   }
1662   // Overpass (error) methods are not concrete if k is abstract.
1663   if (m->is_overpass() && k != nullptr) {
1664      return !k->is_abstract();
1665   }
1666   // Note "true" is conservative answer: overpass clause is false if k == nullptr,
1667   // implies return true if answer depends on overpass clause.
1668   return true;
1669  }
1670 
1671 Klass* Dependencies::find_finalizable_subclass(InstanceKlass* ik) {
1672   for (ClassHierarchyIterator iter(ik); !iter.done(); iter.next()) {
1673     Klass* sub = iter.klass();
1674     if (sub->has_finalizer() && !sub->is_interface()) {
1675       return sub;
1676     }
1677   }
1678   return nullptr; // not found
1679 }
1680 
1681 bool Dependencies::is_concrete_klass(ciInstanceKlass* k) {
1682   if (k->is_abstract())  return false;
1683   // We could also return false if k does not yet appear to be
1684   // instantiated, if the VM version supports this distinction also.
1685   //if (k->is_not_instantiated())  return false;
1686   return true;
1687 }
1688 
1689 bool Dependencies::has_finalizable_subclass(ciInstanceKlass* k) {
1690   return k->has_finalizable_subclass();
1691 }
1692 
1693 // Any use of the contents (bytecodes) of a method must be
1694 // marked by an "evol_method" dependency, if those contents
1695 // can change.  (Note: A method is always dependent on itself.)
1696 Klass* Dependencies::check_evol_method(Method* m) {
1697   assert(must_be_in_vm(), "raw oops here");
1698   // Did somebody do a JVMTI RedefineClasses while our backs were turned?
1699   // Or is there a now a breakpoint?
1700   // (Assumes compiled code cannot handle bkpts; change if UseFastBreakpoints.)
1701   if (m->is_old()
1702       || m->number_of_breakpoints() > 0) {
1703     return m->method_holder();
1704   } else {
1705     return nullptr;
1706   }
1707 }
1708 
1709 // This is a strong assertion:  It is that the given type
1710 // has no subtypes whatever.  It is most useful for
1711 // optimizing checks on reflected types or on array types.
1712 // (Checks on types which are derived from real instances
1713 // can be optimized more strongly than this, because we
1714 // know that the checked type comes from a concrete type,
1715 // and therefore we can disregard abstract types.)
1716 Klass* Dependencies::check_leaf_type(InstanceKlass* ctxk) {
1717   assert(must_be_in_vm(), "raw oops here");
1718   assert_locked_or_safepoint(Compile_lock);
1719   Klass* sub = ctxk->subklass();
1720   if (sub != nullptr) {
1721     return sub;
1722   } else if (ctxk->nof_implementors() != 0) {
1723     // if it is an interface, it must be unimplemented
1724     // (if it is not an interface, nof_implementors is always zero)
1725     InstanceKlass* impl = ctxk->implementor();
1726     assert(impl != nullptr, "must be set");
1727     return impl;
1728   } else {
1729     return nullptr;
1730   }
1731 }
1732 
1733 // Test the assertion that conck is the only concrete subtype* of ctxk.
1734 // The type conck itself is allowed to have have further concrete subtypes.
1735 // This allows the compiler to narrow occurrences of ctxk by conck,
1736 // when dealing with the types of actual instances.
1737 Klass* Dependencies::check_abstract_with_unique_concrete_subtype(InstanceKlass* ctxk,
1738                                                                  Klass* conck,
1739                                                                  NewKlassDepChange* changes) {
1740   ConcreteSubtypeFinder wf(conck);
1741   Klass* k = wf.find_witness(ctxk, changes);
1742   return k;
1743 }
1744 
1745 
1746 // Find the unique concrete proper subtype of ctxk, or nullptr if there
1747 // is more than one concrete proper subtype.  If there are no concrete
1748 // proper subtypes, return ctxk itself, whether it is concrete or not.
1749 // The returned subtype is allowed to have have further concrete subtypes.
1750 // That is, return CC1 for CX > CC1 > CC2, but nullptr for CX > { CC1, CC2 }.
1751 Klass* Dependencies::find_unique_concrete_subtype(InstanceKlass* ctxk) {
1752   ConcreteSubtypeFinder wf(ctxk);  // Ignore ctxk when walking.
1753   wf.record_witnesses(1);          // Record one other witness when walking.
1754   Klass* wit = wf.find_witness(ctxk);
1755   if (wit != nullptr)  return nullptr;   // Too many witnesses.
1756   Klass* conck = wf.participant(0);
1757   if (conck == nullptr) {
1758     return ctxk;                   // Return ctxk as a flag for "no subtypes".
1759   } else {
1760 #ifndef PRODUCT
1761     // Make sure the dependency mechanism will pass this discovery:
1762     if (VerifyDependencies) {
1763       // Turn off dependency tracing while actually testing deps.
1764       FlagSetting fs(_verify_in_progress, true);
1765       if (!Dependencies::is_concrete_klass(ctxk)) {
1766         guarantee(nullptr == (void *)
1767                   check_abstract_with_unique_concrete_subtype(ctxk, conck),
1768                   "verify dep.");
1769       }
1770     }
1771 #endif //PRODUCT
1772     return conck;
1773   }
1774 }
1775 
1776 // Try to determine whether root method in some context is concrete or not based on the information about the unique method
1777 // in that context. It exploits the fact that concrete root method is always inherited into the context when there's a unique method.
1778 // Hence, unique method holder is always a supertype of the context class when root method is concrete.
1779 // Examples for concrete_root_method
1780 //      C (C.m uniqm)
1781 //      |
1782 //      CX (ctxk) uniqm is inherited into context.
1783 //
1784 //      CX (ctxk) (CX.m uniqm) here uniqm is defined in ctxk.
1785 // Examples for !concrete_root_method
1786 //      CX (ctxk)
1787 //      |
1788 //      C (C.m uniqm) uniqm is in subtype of ctxk.
1789 bool Dependencies::is_concrete_root_method(Method* uniqm, InstanceKlass* ctxk) {
1790   if (uniqm == nullptr) {
1791     return false; // match Dependencies::is_concrete_method() behavior
1792   }
1793   // Theoretically, the "direction" of subtype check matters here.
1794   // On one hand, in case of interface context with a single implementor, uniqm can be in a superclass of the implementor which
1795   // is not related to context class.
1796   // On another hand, uniqm could come from an interface unrelated to the context class, but right now it is not possible:
1797   // it is required that uniqm->method_holder() is the participant (uniqm->method_holder() <: ctxk), hence a default method
1798   // can't be used as unique.
1799   if (ctxk->is_interface()) {
1800     InstanceKlass* implementor = ctxk->implementor();
1801     assert(implementor != ctxk, "single implementor only"); // should have been invalidated earlier
1802     ctxk = implementor;
1803   }
1804   InstanceKlass* holder = uniqm->method_holder();
1805   assert(!holder->is_interface(), "no default methods allowed");
1806   assert(ctxk->is_subclass_of(holder) || holder->is_subclass_of(ctxk), "not related");
1807   return ctxk->is_subclass_of(holder);
1808 }
1809 
1810 // If a class (or interface) has a unique concrete method uniqm, return nullptr.
1811 // Otherwise, return a class that contains an interfering method.
1812 Klass* Dependencies::check_unique_concrete_method(InstanceKlass* ctxk,
1813                                                   Method* uniqm,
1814                                                   NewKlassDepChange* changes) {
1815   ConcreteMethodFinder wf(uniqm, uniqm->method_holder());
1816   Klass* k = wf.find_witness(ctxk, changes);
1817   if (k != nullptr) {
1818     return k;
1819   }
1820   if (!Dependencies::is_concrete_root_method(uniqm, ctxk) || changes != nullptr) {
1821     Klass* conck = find_witness_AME(ctxk, uniqm, changes);
1822     if (conck != nullptr) {
1823       // Found a concrete subtype 'conck' which does not override abstract root method.
1824       return conck;
1825     }
1826   }
1827   return nullptr;
1828 }
1829 
1830 Klass* Dependencies::check_unique_implementor(InstanceKlass* ctxk, Klass* uniqk, NewKlassDepChange* changes) {
1831   assert(ctxk->is_interface(), "sanity");
1832   assert(ctxk->nof_implementors() > 0, "no implementors");
1833   if (ctxk->nof_implementors() == 1) {
1834     assert(ctxk->implementor() == uniqk, "sanity");
1835     return nullptr;
1836   }
1837   return ctxk; // no unique implementor
1838 }
1839 
1840 // Search for AME.
1841 // There are two version of checks.
1842 //   1) Spot checking version(Classload time). Newly added class is checked for AME.
1843 //      Checks whether abstract/overpass method is inherited into/declared in newly added concrete class.
1844 //   2) Compile time analysis for abstract/overpass(abstract klass) root_m. The non uniqm subtrees are checked for concrete classes.
1845 Klass* Dependencies::find_witness_AME(InstanceKlass* ctxk, Method* m, KlassDepChange* changes) {
1846   if (m != nullptr) {
1847     if (changes != nullptr) {
1848       // Spot checking version.
1849       ConcreteMethodFinder wf(m);
1850       Klass* new_type = changes->as_new_klass_change()->new_type();
1851       if (wf.witnessed_reabstraction_in_supers(new_type)) {
1852         return new_type;
1853       }
1854     } else {
1855       // Note: It is required that uniqm->method_holder() is the participant (see ClassHierarchyWalker::found_method()).
1856       ConcreteSubtypeFinder wf(m->method_holder());
1857       Klass* conck = wf.find_witness(ctxk);
1858       if (conck != nullptr) {
1859         Method* cm = InstanceKlass::cast(conck)->find_instance_method(m->name(), m->signature(), Klass::PrivateLookupMode::skip);
1860         if (!Dependencies::is_concrete_method(cm, conck)) {
1861           return conck;
1862         }
1863       }
1864     }
1865   }
1866   return nullptr;
1867 }
1868 
1869 // This function is used by find_unique_concrete_method(non vtable based)
1870 // to check whether subtype method overrides the base method.
1871 static bool overrides(Method* sub_m, Method* base_m) {
1872   assert(base_m != nullptr, "base method should be non null");
1873   if (sub_m == nullptr) {
1874     return false;
1875   }
1876   /**
1877    *  If base_m is public or protected then sub_m always overrides.
1878    *  If base_m is !public, !protected and !private (i.e. base_m is package private)
1879    *  then sub_m should be in the same package as that of base_m.
1880    *  For package private base_m this is conservative approach as it allows only subset of all allowed cases in
1881    *  the jvm specification.
1882    **/
1883   if (base_m->is_public() || base_m->is_protected() ||
1884       base_m->method_holder()->is_same_class_package(sub_m->method_holder())) {
1885     return true;
1886   }
1887   return false;
1888 }
1889 
1890 // Find the set of all non-abstract methods under ctxk that match m.
1891 // (The method m must be defined or inherited in ctxk.)
1892 // Include m itself in the set, unless it is abstract.
1893 // If this set has exactly one element, return that element.
1894 Method* Dependencies::find_unique_concrete_method(InstanceKlass* ctxk, Method* m, Klass** participant) {
1895   // Return nullptr if m is marked old; must have been a redefined method.
1896   if (m->is_old()) {
1897     return nullptr;
1898   }
1899   if (m->is_default_method()) {
1900     return nullptr; // not supported
1901   }
1902   assert(verify_method_context(ctxk, m), "proper context");
1903   ConcreteMethodFinder wf(m);
1904   wf.record_witnesses(1);
1905   Klass* wit = wf.find_witness(ctxk);
1906   if (wit != nullptr)  return nullptr;  // Too many witnesses.
1907   Method* fm = wf.found_method(0);  // Will be nullptr if num_parts == 0.
1908   if (participant != nullptr) {
1909     (*participant) = wf.participant(0);
1910   }
1911   if (!Dependencies::is_concrete_method(fm, nullptr)) {
1912     fm = nullptr; // ignore abstract methods
1913   }
1914   if (Dependencies::is_concrete_method(m, ctxk)) {
1915     if (fm == nullptr) {
1916       // It turns out that m was always the only implementation.
1917       fm = m;
1918     } else if (fm != m) {
1919       // Two conflicting implementations after all.
1920       // (This can happen if m is inherited into ctxk and fm overrides it.)
1921       return nullptr;
1922     }
1923   } else if (Dependencies::find_witness_AME(ctxk, fm) != nullptr) {
1924     // Found a concrete subtype which does not override abstract root method.
1925     return nullptr;
1926   } else if (!overrides(fm, m)) {
1927     // Found method doesn't override abstract root method.
1928     return nullptr;
1929   }
1930   assert(Dependencies::is_concrete_root_method(fm, ctxk) == Dependencies::is_concrete_method(m, ctxk), "mismatch");
1931 #ifndef PRODUCT
1932   // Make sure the dependency mechanism will pass this discovery:
1933   if (VerifyDependencies && fm != nullptr) {
1934     guarantee(nullptr == (void *)check_unique_concrete_method(ctxk, fm),
1935               "verify dep.");
1936   }
1937 #endif //PRODUCT
1938   return fm;
1939 }
1940 
1941 // If a class (or interface) has a unique concrete method uniqm, return nullptr.
1942 // Otherwise, return a class that contains an interfering method.
1943 Klass* Dependencies::check_unique_concrete_method(InstanceKlass* ctxk,
1944                                                   Method* uniqm,
1945                                                   Klass* resolved_klass,
1946                                                   Method* resolved_method,
1947                                                   KlassDepChange* changes) {
1948   assert(!ctxk->is_interface() || ctxk == resolved_klass, "sanity");
1949   assert(!resolved_method->can_be_statically_bound() || resolved_method == uniqm, "sanity");
1950   assert(resolved_klass->is_subtype_of(resolved_method->method_holder()), "sanity");
1951 
1952   if (!InstanceKlass::cast(resolved_klass)->is_linked() ||
1953       !resolved_method->method_holder()->is_linked() ||
1954       resolved_method->can_be_statically_bound()) {
1955     // Dependency is redundant, but benign. Just keep it to avoid unnecessary recompilation.
1956     return nullptr; // no vtable index available
1957   }
1958 
1959   LinkedConcreteMethodFinder mf(InstanceKlass::cast(resolved_klass), resolved_method, uniqm);
1960   return mf.find_witness(ctxk, changes);
1961 }
1962 
1963 // Find the set of all non-abstract methods under ctxk that match m.
1964 // (The method m must be defined or inherited in ctxk.)
1965 // Include m itself in the set, unless it is abstract.
1966 // If this set has exactly one element, return that element.
1967 // Not yet linked subclasses of ctxk are ignored since they don't have any instances yet.
1968 // Additionally, resolved_klass and resolved_method complete the description of the call site being analyzed.
1969 Method* Dependencies::find_unique_concrete_method(InstanceKlass* ctxk, Method* m, Klass* resolved_klass, Method* resolved_method) {
1970   // Return nullptr if m is marked old; must have been a redefined method.
1971   if (m->is_old()) {
1972     return nullptr;
1973   }
1974   if (!InstanceKlass::cast(resolved_klass)->is_linked() ||
1975       !resolved_method->method_holder()->is_linked() ||
1976       resolved_method->can_be_statically_bound()) {
1977     return m; // nothing to do: no witness under ctxk
1978   }
1979   LinkedConcreteMethodFinder wf(InstanceKlass::cast(resolved_klass), resolved_method);
1980   assert(Dependencies::verify_method_context(ctxk, m), "proper context");
1981   wf.record_witnesses(1);
1982   Klass* wit = wf.find_witness(ctxk);
1983   if (wit != nullptr) {
1984     return nullptr;  // Too many witnesses.
1985   }
1986   // p == nullptr when no participants are found (wf.num_participants() == 0).
1987   // fm == nullptr case has 2 meanings:
1988   //  * when p == nullptr: no method found;
1989   //  * when p != nullptr: AbstractMethodError-throwing method found.
1990   // Also, found method should always be accompanied by a participant class.
1991   Klass*   p = wf.participant(0);
1992   Method* fm = wf.found_method(0);
1993   assert(fm == nullptr || p != nullptr, "no participant");
1994   // Normalize all error-throwing cases to nullptr.
1995   if (fm == Universe::throw_illegal_access_error() ||
1996       fm == Universe::throw_no_such_method_error() ||
1997       !Dependencies::is_concrete_method(fm, p)) {
1998     fm = nullptr; // error-throwing method
1999   }
2000   if (Dependencies::is_concrete_method(m, ctxk)) {
2001     if (p == nullptr) {
2002       // It turns out that m was always the only implementation.
2003       assert(fm == nullptr, "sanity");
2004       fm = m;
2005     }
2006   }
2007 #ifndef PRODUCT
2008   // Make sure the dependency mechanism will pass this discovery:
2009   if (VerifyDependencies && fm != nullptr) {
2010     guarantee(nullptr == check_unique_concrete_method(ctxk, fm, resolved_klass, resolved_method),
2011               "verify dep.");
2012   }
2013 #endif // PRODUCT
2014   assert(fm == nullptr || !fm->is_abstract(), "sanity");
2015   // Old CHA conservatively reports concrete methods in abstract classes
2016   // irrespective of whether they have concrete subclasses or not.
2017   // Also, abstract root method case is not fully supported.
2018 #ifdef ASSERT
2019   Klass*  uniqp = nullptr;
2020   Method* uniqm = Dependencies::find_unique_concrete_method(ctxk, m, &uniqp);
2021   assert(uniqm == nullptr || uniqm == fm ||
2022          m->is_abstract() ||
2023          uniqm->method_holder()->is_abstract() ||
2024          (fm == nullptr && uniqm != nullptr && uniqp != nullptr && !InstanceKlass::cast(uniqp)->is_linked()),
2025          "sanity");
2026 #endif // ASSERT
2027   return fm;
2028 }
2029 
2030 Klass* Dependencies::check_has_no_finalizable_subclasses(InstanceKlass* ctxk, NewKlassDepChange* changes) {
2031   InstanceKlass* search_at = ctxk;
2032   if (changes != nullptr) {
2033     search_at = changes->new_type(); // just look at the new bit
2034   }
2035   return find_finalizable_subclass(search_at);
2036 }
2037 
2038 Klass* Dependencies::check_call_site_target_value(oop call_site, oop method_handle, CallSiteDepChange* changes) {
2039   assert(call_site != nullptr, "sanity");
2040   assert(method_handle != nullptr, "sanity");
2041   assert(call_site->is_a(vmClasses::CallSite_klass()),     "sanity");
2042 
2043   if (changes == nullptr) {
2044     // Validate all CallSites
2045     if (java_lang_invoke_CallSite::target(call_site) != method_handle)
2046       return call_site->klass();  // assertion failed
2047   } else {
2048     // Validate the given CallSite
2049     if (call_site == changes->call_site() && java_lang_invoke_CallSite::target(call_site) != changes->method_handle()) {
2050       assert(method_handle != changes->method_handle(), "must be");
2051       return call_site->klass();  // assertion failed
2052     }
2053   }
2054   return nullptr;  // assertion still valid
2055 }
2056 
2057 void Dependencies::DepStream::trace_and_log_witness(Klass* witness) {
2058   if (_verify_in_progress) return;  // don't log
2059   if (witness != nullptr) {
2060     LogTarget(Debug, dependencies) lt;
2061     if (lt.is_enabled()) {
2062       LogStream ls(&lt);
2063       print_dependency(&ls, witness, /*verbose=*/ true);
2064     }
2065     // The following is a no-op unless logging is enabled:
2066     log_dependency(witness);
2067   }
2068 }
2069 
2070 Klass* Dependencies::DepStream::check_new_klass_dependency(NewKlassDepChange* changes) {
2071   assert_locked_or_safepoint(Compile_lock);
2072   Dependencies::check_valid_dependency_type(type());
2073 
2074   Klass* witness = nullptr;
2075   switch (type()) {
2076   case evol_method:
2077     witness = check_evol_method(method_argument(0));
2078     break;
2079   case leaf_type:
2080     witness = check_leaf_type(context_type());
2081     break;
2082   case abstract_with_unique_concrete_subtype:
2083     witness = check_abstract_with_unique_concrete_subtype(context_type(), type_argument(1), changes);
2084     break;
2085   case unique_concrete_method_2:
2086     witness = check_unique_concrete_method(context_type(), method_argument(1), changes);
2087     break;
2088   case unique_concrete_method_4:
2089     witness = check_unique_concrete_method(context_type(), method_argument(1), type_argument(2), method_argument(3), changes);
2090     break;
2091   case unique_implementor:
2092     witness = check_unique_implementor(context_type(), type_argument(1), changes);
2093     break;
2094   case no_finalizable_subclasses:
2095     witness = check_has_no_finalizable_subclasses(context_type(), changes);
2096     break;
2097   default:
2098     witness = nullptr;
2099     break;
2100   }
2101   trace_and_log_witness(witness);
2102   return witness;
2103 }
2104 
2105 Klass* Dependencies::DepStream::check_klass_init_dependency(KlassInitDepChange* changes) {
2106   assert_locked_or_safepoint(Compile_lock);
2107   Dependencies::check_valid_dependency_type(type());
2108 
2109   // No new types added. Only unique_concrete_method_4 is sensitive to class initialization changes.
2110   Klass* witness = nullptr;
2111   switch (type()) {
2112   case unique_concrete_method_4:
2113     witness = check_unique_concrete_method(context_type(), method_argument(1), type_argument(2), method_argument(3), changes);
2114     break;
2115   default:
2116     witness = nullptr;
2117     break;
2118   }
2119   trace_and_log_witness(witness);
2120   return witness;
2121 }
2122 
2123 Klass* Dependencies::DepStream::check_klass_dependency(KlassDepChange* changes) {
2124   assert_locked_or_safepoint(Compile_lock);
2125   Dependencies::check_valid_dependency_type(type());
2126 
2127   if (changes != nullptr) {
2128     if (changes->is_klass_init_change()) {
2129       return check_klass_init_dependency(changes->as_klass_init_change());
2130     } else {
2131       return check_new_klass_dependency(changes->as_new_klass_change());
2132     }
2133   } else {
2134     Klass* witness = check_new_klass_dependency(nullptr);
2135     // check_klass_init_dependency duplicates check_new_klass_dependency checks when class hierarchy change info is absent.
2136     assert(witness != nullptr || check_klass_init_dependency(nullptr) == nullptr, "missed dependency");
2137     return witness;
2138   }
2139 }
2140 
2141 Klass* Dependencies::DepStream::check_call_site_dependency(CallSiteDepChange* changes) {
2142   assert_locked_or_safepoint(Compile_lock);
2143   Dependencies::check_valid_dependency_type(type());
2144 
2145   Klass* witness = nullptr;
2146   switch (type()) {
2147   case call_site_target_value:
2148     witness = check_call_site_target_value(argument_oop(0), argument_oop(1), changes);
2149     break;
2150   default:
2151     witness = nullptr;
2152     break;
2153   }
2154   trace_and_log_witness(witness);
2155   return witness;
2156 }
2157 
2158 
2159 Klass* Dependencies::DepStream::spot_check_dependency_at(DepChange& changes) {
2160   // Handle klass dependency
2161   if (changes.is_klass_change() && changes.as_klass_change()->involves_context(context_type()))
2162     return check_klass_dependency(changes.as_klass_change());
2163 
2164   // Handle CallSite dependency
2165   if (changes.is_call_site_change())
2166     return check_call_site_dependency(changes.as_call_site_change());
2167 
2168   // irrelevant dependency; skip it
2169   return nullptr;
2170 }
2171 
2172 
2173 void DepChange::print() { print_on(tty); }
2174 
2175 void DepChange::print_on(outputStream* st) {
2176   int nsup = 0, nint = 0;
2177   for (ContextStream str(*this); str.next(); ) {
2178     InstanceKlass* k = str.klass();
2179     switch (str.change_type()) {
2180     case Change_new_type:
2181       st->print_cr("  dependee = %s", k->external_name());
2182       break;
2183     case Change_new_sub:
2184       if (!WizardMode) {
2185         ++nsup;
2186       } else {
2187         st->print_cr("  context super = %s", k->external_name());
2188       }
2189       break;
2190     case Change_new_impl:
2191       if (!WizardMode) {
2192         ++nint;
2193       } else {
2194         st->print_cr("  context interface = %s", k->external_name());
2195       }
2196       break;
2197     default:
2198       break;
2199     }
2200   }
2201   if (nsup + nint != 0) {
2202     st->print_cr("  context supers = %d, interfaces = %d", nsup, nint);
2203   }
2204 }
2205 
2206 void DepChange::ContextStream::start() {
2207   InstanceKlass* type = (_changes.is_klass_change() ? _changes.as_klass_change()->type() : (InstanceKlass*) nullptr);
2208   _change_type = (type == nullptr ? NO_CHANGE : Start_Klass);
2209   _klass = type;
2210   _ti_base = nullptr;
2211   _ti_index = 0;
2212   _ti_limit = 0;
2213 }
2214 
2215 bool DepChange::ContextStream::next() {
2216   switch (_change_type) {
2217   case Start_Klass:             // initial state; _klass is the new type
2218     _ti_base = _klass->transitive_interfaces();
2219     _ti_index = 0;
2220     _change_type = Change_new_type;
2221     return true;
2222   case Change_new_type:
2223     // fall through:
2224     _change_type = Change_new_sub;
2225   case Change_new_sub:
2226     // 6598190: brackets workaround Sun Studio C++ compiler bug 6629277
2227     {
2228       _klass = _klass->java_super();
2229       if (_klass != nullptr) {
2230         return true;
2231       }
2232     }
2233     // else set up _ti_limit and fall through:
2234     _ti_limit = (_ti_base == nullptr) ? 0 : _ti_base->length();
2235     _change_type = Change_new_impl;
2236   case Change_new_impl:
2237     if (_ti_index < _ti_limit) {
2238       _klass = _ti_base->at(_ti_index++);
2239       return true;
2240     }
2241     // fall through:
2242     _change_type = NO_CHANGE;  // iterator is exhausted
2243   case NO_CHANGE:
2244     break;
2245   default:
2246     ShouldNotReachHere();
2247   }
2248   return false;
2249 }
2250 
2251 void KlassDepChange::initialize() {
2252   // entire transaction must be under this lock:
2253   assert_lock_strong(Compile_lock);
2254 
2255   // Mark all dependee and all its superclasses
2256   // Mark transitive interfaces
2257   for (ContextStream str(*this); str.next(); ) {
2258     InstanceKlass* d = str.klass();
2259     assert(!d->is_marked_dependent(), "checking");
2260     d->set_is_marked_dependent(true);
2261   }
2262 }
2263 
2264 KlassDepChange::~KlassDepChange() {
2265   // Unmark all dependee and all its superclasses
2266   // Unmark transitive interfaces
2267   for (ContextStream str(*this); str.next(); ) {
2268     InstanceKlass* d = str.klass();
2269     d->set_is_marked_dependent(false);
2270   }
2271 }
2272 
2273 bool KlassDepChange::involves_context(Klass* k) {
2274   if (k == nullptr || !k->is_instance_klass()) {
2275     return false;
2276   }
2277   InstanceKlass* ik = InstanceKlass::cast(k);
2278   bool is_contained = ik->is_marked_dependent();
2279   assert(is_contained == type()->is_subtype_of(k),
2280          "correct marking of potential context types");
2281   return is_contained;
2282 }
2283 
2284 void Dependencies::print_statistics() {
2285   AbstractClassHierarchyWalker::print_statistics();
2286 }
2287 
2288 void AbstractClassHierarchyWalker::print_statistics() {
2289   if (UsePerfData) {
2290     jlong deps_find_witness_calls   = _perf_find_witness_anywhere_calls_count->get_value();
2291     jlong deps_find_witness_steps   = _perf_find_witness_anywhere_steps_count->get_value();
2292     jlong deps_find_witness_singles = _perf_find_witness_in_calls_count->get_value();
2293 
2294     ttyLocker ttyl;
2295     tty->print_cr("Dependency check (find_witness) "
2296                   "calls=" JLONG_FORMAT ", steps=" JLONG_FORMAT " (avg=%.1f), singles=" JLONG_FORMAT,
2297                   deps_find_witness_calls,
2298                   deps_find_witness_steps,
2299                   (double)deps_find_witness_steps / deps_find_witness_calls,
2300                   deps_find_witness_singles);
2301     if (xtty != nullptr) {
2302       xtty->elem("deps_find_witness calls='" JLONG_FORMAT "' steps='" JLONG_FORMAT "' singles='" JLONG_FORMAT "'",
2303                  deps_find_witness_calls,
2304                  deps_find_witness_steps,
2305                  deps_find_witness_singles);
2306     }
2307   }
2308 }
2309 
2310 CallSiteDepChange::CallSiteDepChange(Handle call_site, Handle method_handle) :
2311   _call_site(call_site),
2312   _method_handle(method_handle) {
2313   assert(_call_site()->is_a(vmClasses::CallSite_klass()), "must be");
2314   assert(_method_handle.is_null() || _method_handle()->is_a(vmClasses::MethodHandle_klass()), "must be");
2315 }
2316 
2317 void dependencies_init() {
2318   AbstractClassHierarchyWalker::init();
2319 }