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