dependencies.cpp

/*
 * Copyright (c) 2005, 2025, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 *
 */

#include "ci/ciArrayKlass.hpp"
#include "ci/ciEnv.hpp"
#include "ci/ciKlass.hpp"
#include "ci/ciMethod.hpp"
#include "classfile/javaClasses.inline.hpp"
#include "classfile/vmClasses.hpp"
#include "code/dependencies.hpp"
#include "compiler/compileLog.hpp"
#include "compiler/compileBroker.hpp"
#include "compiler/compileTask.hpp"
#include "memory/resourceArea.hpp"
#include "oops/klass.hpp"
#include "oops/oop.inline.hpp"
#include "oops/method.inline.hpp"
#include "oops/objArrayKlass.hpp"
#include "runtime/flags/flagSetting.hpp"
#include "runtime/handles.hpp"
#include "runtime/handles.inline.hpp"
#include "runtime/javaThread.inline.hpp"
#include "runtime/jniHandles.inline.hpp"
#include "runtime/mutexLocker.hpp"
#include "runtime/perfData.hpp"
#include "runtime/vmThread.hpp"
#include "utilities/copy.hpp"


#ifdef ASSERT
static bool must_be_in_vm() {
  Thread* thread = Thread::current();
  if (thread->is_Java_thread()) {
    return JavaThread::cast(thread)->thread_state() == _thread_in_vm;
  } else {
    return true;  // Could be VMThread or GC thread
  }
}
#endif //ASSERT

bool Dependencies::_verify_in_progress = false;  // don't -Xlog:dependencies

void Dependencies::initialize(ciEnv* env) {
  Arena* arena = env->arena();
  _oop_recorder = env->oop_recorder();
  _log = env->log();
  _dep_seen = new(arena) GrowableArray<int>(arena, 500, 0, 0);
#if INCLUDE_JVMCI
  _using_dep_values = false;
#endif
  DEBUG_ONLY(_deps[end_marker] = nullptr);
  for (int i = (int)FIRST_TYPE; i < (int)TYPE_LIMIT; i++) {
    _deps[i] = new(arena) GrowableArray<ciBaseObject*>(arena, 10, 0, nullptr);
  }
  _content_bytes = nullptr;
  _size_in_bytes = (size_t)-1;

  assert(TYPE_LIMIT <= (1<<LG2_TYPE_LIMIT), "sanity");
}

void Dependencies::assert_evol_method(ciMethod* m) {
  assert_common_1(evol_method, m);
}

void Dependencies::assert_leaf_type(ciKlass* ctxk) {
  if (ctxk->is_array_klass()) {
    // As a special case, support this assertion on an array type,
    // which reduces to an assertion on its element type.
    // Note that this cannot be done with assertions that
    // relate to concreteness or abstractness.
    ciType* elemt = ctxk->as_array_klass()->base_element_type();
    if (!elemt->is_instance_klass())  return;   // Ex:  int[][]
    ctxk = elemt->as_instance_klass();
    //if (ctxk->is_final())  return;            // Ex:  String[][]
  }
  check_ctxk(ctxk);
  assert_common_1(leaf_type, ctxk);
}

void Dependencies::assert_abstract_with_unique_concrete_subtype(ciKlass* ctxk, ciKlass* conck) {
  check_ctxk_abstract(ctxk);
  assert_common_2(abstract_with_unique_concrete_subtype, ctxk, conck);
}

void Dependencies::assert_unique_concrete_method(ciKlass* ctxk, ciMethod* uniqm) {
  check_ctxk(ctxk);
  check_unique_method(ctxk, uniqm);
  assert_common_2(unique_concrete_method_2, ctxk, uniqm);
}

void Dependencies::assert_unique_concrete_method(ciKlass* ctxk, ciMethod* uniqm, ciKlass* resolved_klass, ciMethod* resolved_method) {
  check_ctxk(ctxk);
  check_unique_method(ctxk, uniqm);
  assert_common_4(unique_concrete_method_4, ctxk, uniqm, resolved_klass, resolved_method);
}

void Dependencies::assert_unique_implementor(ciInstanceKlass* ctxk, ciInstanceKlass* uniqk) {
  check_ctxk(ctxk);
  check_unique_implementor(ctxk, uniqk);
  assert_common_2(unique_implementor, ctxk, uniqk);
}

void Dependencies::assert_has_no_finalizable_subclasses(ciKlass* ctxk) {
  check_ctxk(ctxk);
  assert_common_1(no_finalizable_subclasses, ctxk);
}

void Dependencies::assert_call_site_target_value(ciCallSite* call_site, ciMethodHandle* method_handle) {
  assert_common_2(call_site_target_value, call_site, method_handle);
}

#if INCLUDE_JVMCI

Dependencies::Dependencies(Arena* arena, OopRecorder* oop_recorder, CompileLog* log) {
  _oop_recorder = oop_recorder;
  _log = log;
  _dep_seen = new(arena) GrowableArray<int>(arena, 500, 0, 0);
  _using_dep_values = true;
  DEBUG_ONLY(_dep_values[end_marker] = nullptr);
  for (int i = (int)FIRST_TYPE; i < (int)TYPE_LIMIT; i++) {
    _dep_values[i] = new(arena) GrowableArray<DepValue>(arena, 10, 0, DepValue());
  }
  _content_bytes = nullptr;
  _size_in_bytes = (size_t)-1;

  assert(TYPE_LIMIT <= (1<<LG2_TYPE_LIMIT), "sanity");
}

void Dependencies::assert_evol_method(Method* m) {
  assert_common_1(evol_method, DepValue(_oop_recorder, m));
}

void Dependencies::assert_has_no_finalizable_subclasses(Klass* ctxk) {
  check_ctxk(ctxk);
  assert_common_1(no_finalizable_subclasses, DepValue(_oop_recorder, ctxk));
}

void Dependencies::assert_leaf_type(Klass* ctxk) {
  if (ctxk->is_array_klass()) {
    // As a special case, support this assertion on an array type,
    // which reduces to an assertion on its element type.
    // Note that this cannot be done with assertions that
    // relate to concreteness or abstractness.
    BasicType elemt = ArrayKlass::cast(ctxk)->element_type();
    if (is_java_primitive(elemt))  return;   // Ex:  int[][]
    ctxk = ObjArrayKlass::cast(ctxk)->bottom_klass();
    //if (ctxk->is_final())  return;            // Ex:  String[][]
  }
  check_ctxk(ctxk);
  assert_common_1(leaf_type, DepValue(_oop_recorder, ctxk));
}

void Dependencies::assert_abstract_with_unique_concrete_subtype(Klass* ctxk, Klass* conck) {
  check_ctxk_abstract(ctxk);
  DepValue ctxk_dv(_oop_recorder, ctxk);
  DepValue conck_dv(_oop_recorder, conck, &ctxk_dv);
  assert_common_2(abstract_with_unique_concrete_subtype, ctxk_dv, conck_dv);
}

void Dependencies::assert_unique_implementor(InstanceKlass* ctxk, InstanceKlass* uniqk) {
  check_ctxk(ctxk);
  assert(ctxk->is_interface(), "not an interface");
  assert(ctxk->implementor() == uniqk, "not a unique implementor");
  assert_common_2(unique_implementor, DepValue(_oop_recorder, ctxk), DepValue(_oop_recorder, uniqk));
}

void Dependencies::assert_unique_concrete_method(Klass* ctxk, Method* uniqm) {
  check_ctxk(ctxk);
  check_unique_method(ctxk, uniqm);
  assert_common_2(unique_concrete_method_2, DepValue(_oop_recorder, ctxk), DepValue(_oop_recorder, uniqm));
}

void Dependencies::assert_call_site_target_value(oop call_site, oop method_handle) {
  assert_common_2(call_site_target_value, DepValue(_oop_recorder, JNIHandles::make_local(call_site)), DepValue(_oop_recorder, JNIHandles::make_local(method_handle)));
}

#endif // INCLUDE_JVMCI


// Helper function.  If we are adding a new dep. under ctxk2,
// try to find an old dep. under a broader* ctxk1.  If there is
//
bool Dependencies::maybe_merge_ctxk(GrowableArray<ciBaseObject*>* deps,
                                    int ctxk_i, ciKlass* ctxk2) {
  ciKlass* ctxk1 = deps->at(ctxk_i)->as_metadata()->as_klass();
  if (ctxk2->is_subtype_of(ctxk1)) {
    return true;  // success, and no need to change
  } else if (ctxk1->is_subtype_of(ctxk2)) {
    // new context class fully subsumes previous one
    deps->at_put(ctxk_i, ctxk2);
    return true;
  } else {
    return false;
  }
}

void Dependencies::assert_common_1(DepType dept, ciBaseObject* x) {
  assert(dep_args(dept) == 1, "sanity");
  log_dependency(dept, x);
  GrowableArray<ciBaseObject*>* deps = _deps[dept];

  // see if the same (or a similar) dep is already recorded
  if (note_dep_seen(dept, x)) {
    assert(deps->find(x) >= 0, "sanity");
  } else {
    deps->append(x);
  }
}

void Dependencies::assert_common_2(DepType dept,
                                   ciBaseObject* x0, ciBaseObject* x1) {
  assert(dep_args(dept) == 2, "sanity");
  log_dependency(dept, x0, x1);
  GrowableArray<ciBaseObject*>* deps = _deps[dept];

  // see if the same (or a similar) dep is already recorded
  bool has_ctxk = has_explicit_context_arg(dept);
  if (has_ctxk) {
    assert(dep_context_arg(dept) == 0, "sanity");
    if (note_dep_seen(dept, x1)) {
      // look in this bucket for redundant assertions
      const int stride = 2;
      for (int i = deps->length(); (i -= stride) >= 0; ) {
        ciBaseObject* y1 = deps->at(i+1);
        if (x1 == y1) {  // same subject; check the context
          if (maybe_merge_ctxk(deps, i+0, x0->as_metadata()->as_klass())) {
            return;
          }
        }
      }
    }
  } else {
    bool dep_seen_x0 = note_dep_seen(dept, x0); // records x0 for future queries
    bool dep_seen_x1 = note_dep_seen(dept, x1); // records x1 for future queries
    if (dep_seen_x0 && dep_seen_x1) {
      // look in this bucket for redundant assertions
      const int stride = 2;
      for (int i = deps->length(); (i -= stride) >= 0; ) {
        ciBaseObject* y0 = deps->at(i+0);
        ciBaseObject* y1 = deps->at(i+1);
        if (x0 == y0 && x1 == y1) {
          return;
        }
      }
    }
  }

  // append the assertion in the correct bucket:
  deps->append(x0);
  deps->append(x1);
}

void Dependencies::assert_common_4(DepType dept,
                                   ciKlass* ctxk, ciBaseObject* x1, ciBaseObject* x2, ciBaseObject* x3) {
  assert(has_explicit_context_arg(dept), "sanity");
  assert(dep_context_arg(dept) == 0, "sanity");
  assert(dep_args(dept) == 4, "sanity");
  log_dependency(dept, ctxk, x1, x2, x3);
  GrowableArray<ciBaseObject*>* deps = _deps[dept];

  // see if the same (or a similar) dep is already recorded
  bool dep_seen_x1 = note_dep_seen(dept, x1); // records x1 for future queries
  bool dep_seen_x2 = note_dep_seen(dept, x2); // records x2 for future queries
  bool dep_seen_x3 = note_dep_seen(dept, x3); // records x3 for future queries
  if (dep_seen_x1 && dep_seen_x2 && dep_seen_x3) {
    // look in this bucket for redundant assertions
    const int stride = 4;
    for (int i = deps->length(); (i -= stride) >= 0; ) {
      ciBaseObject* y1 = deps->at(i+1);
      ciBaseObject* y2 = deps->at(i+2);
      ciBaseObject* y3 = deps->at(i+3);
      if (x1 == y1 && x2 == y2 && x3 == y3) {  // same subjects; check the context
        if (maybe_merge_ctxk(deps, i+0, ctxk)) {
          return;
        }
      }
    }
  }
  // append the assertion in the correct bucket:
  deps->append(ctxk);
  deps->append(x1);
  deps->append(x2);
  deps->append(x3);
}

#if INCLUDE_JVMCI
bool Dependencies::maybe_merge_ctxk(GrowableArray<DepValue>* deps,
                                    int ctxk_i, DepValue ctxk2_dv) {
  Klass* ctxk1 = deps->at(ctxk_i).as_klass(_oop_recorder);
  Klass* ctxk2 = ctxk2_dv.as_klass(_oop_recorder);
  if (ctxk2->is_subtype_of(ctxk1)) {
    return true;  // success, and no need to change
  } else if (ctxk1->is_subtype_of(ctxk2)) {
    // new context class fully subsumes previous one
    deps->at_put(ctxk_i, ctxk2_dv);
    return true;
  } else {
    return false;
  }
}

void Dependencies::assert_common_1(DepType dept, DepValue x) {
  assert(dep_args(dept) == 1, "sanity");
  //log_dependency(dept, x);
  GrowableArray<DepValue>* deps = _dep_values[dept];

  // see if the same (or a similar) dep is already recorded
  if (note_dep_seen(dept, x)) {
    assert(deps->find(x) >= 0, "sanity");
  } else {
    deps->append(x);
  }
}

void Dependencies::assert_common_2(DepType dept,
                                   DepValue x0, DepValue x1) {
  assert(dep_args(dept) == 2, "sanity");
  //log_dependency(dept, x0, x1);
  GrowableArray<DepValue>* deps = _dep_values[dept];

  // see if the same (or a similar) dep is already recorded
  bool has_ctxk = has_explicit_context_arg(dept);
  if (has_ctxk) {
    assert(dep_context_arg(dept) == 0, "sanity");
    if (note_dep_seen(dept, x1)) {
      // look in this bucket for redundant assertions
      const int stride = 2;
      for (int i = deps->length(); (i -= stride) >= 0; ) {
        DepValue y1 = deps->at(i+1);
        if (x1 == y1) {  // same subject; check the context
          if (maybe_merge_ctxk(deps, i+0, x0)) {
            return;
          }
        }
      }
    }
  } else {
    bool dep_seen_x0 = note_dep_seen(dept, x0); // records x0 for future queries
    bool dep_seen_x1 = note_dep_seen(dept, x1); // records x1 for future queries
    if (dep_seen_x0 && dep_seen_x1) {
      // look in this bucket for redundant assertions
      const int stride = 2;
      for (int i = deps->length(); (i -= stride) >= 0; ) {
        DepValue y0 = deps->at(i+0);
        DepValue y1 = deps->at(i+1);
        if (x0 == y0 && x1 == y1) {
          return;
        }
      }
    }
  }

  // append the assertion in the correct bucket:
  deps->append(x0);
  deps->append(x1);
}
#endif // INCLUDE_JVMCI

/// Support for encoding dependencies into an nmethod:

void Dependencies::copy_to(nmethod* nm) {
  address beg = nm->dependencies_begin();
  address end = nm->dependencies_end();
  guarantee(end - beg >= (ptrdiff_t) size_in_bytes(), "bad sizing");
  (void)memcpy(beg, content_bytes(), size_in_bytes());
  assert(size_in_bytes() % sizeof(HeapWord) == 0, "copy by words");
}

static int sort_dep(ciBaseObject** p1, ciBaseObject** p2, int narg) {
  for (int i = 0; i < narg; i++) {
    int diff = p1[i]->ident() - p2[i]->ident();
    if (diff != 0)  return diff;
  }
  return 0;
}
static int sort_dep_arg_1(ciBaseObject** p1, ciBaseObject** p2)
{ return sort_dep(p1, p2, 1); }
static int sort_dep_arg_2(ciBaseObject** p1, ciBaseObject** p2)
{ return sort_dep(p1, p2, 2); }
static int sort_dep_arg_3(ciBaseObject** p1, ciBaseObject** p2)
{ return sort_dep(p1, p2, 3); }
static int sort_dep_arg_4(ciBaseObject** p1, ciBaseObject** p2)
{ return sort_dep(p1, p2, 4); }

#if INCLUDE_JVMCI
// metadata deps are sorted before object deps
static int sort_dep_value(Dependencies::DepValue* p1, Dependencies::DepValue* p2, int narg) {
  for (int i = 0; i < narg; i++) {
    int diff = p1[i].sort_key() - p2[i].sort_key();
    if (diff != 0)  return diff;
  }
  return 0;
}
static int sort_dep_value_arg_1(Dependencies::DepValue* p1, Dependencies::DepValue* p2)
{ return sort_dep_value(p1, p2, 1); }
static int sort_dep_value_arg_2(Dependencies::DepValue* p1, Dependencies::DepValue* p2)
{ return sort_dep_value(p1, p2, 2); }
static int sort_dep_value_arg_3(Dependencies::DepValue* p1, Dependencies::DepValue* p2)
{ return sort_dep_value(p1, p2, 3); }
#endif // INCLUDE_JVMCI

void Dependencies::sort_all_deps() {
#if INCLUDE_JVMCI
  if (_using_dep_values) {
    for (int deptv = (int)FIRST_TYPE; deptv < (int)TYPE_LIMIT; deptv++) {
      DepType dept = (DepType)deptv;
      GrowableArray<DepValue>* deps = _dep_values[dept];
      if (deps->length() <= 1)  continue;
      switch (dep_args(dept)) {
      case 1: deps->sort(sort_dep_value_arg_1, 1); break;
      case 2: deps->sort(sort_dep_value_arg_2, 2); break;
      case 3: deps->sort(sort_dep_value_arg_3, 3); break;
      default: ShouldNotReachHere(); break;
      }
    }
    return;
  }
#endif // INCLUDE_JVMCI
  for (int deptv = (int)FIRST_TYPE; deptv < (int)TYPE_LIMIT; deptv++) {
    DepType dept = (DepType)deptv;
    GrowableArray<ciBaseObject*>* deps = _deps[dept];
    if (deps->length() <= 1)  continue;
    switch (dep_args(dept)) {
    case 1: deps->sort(sort_dep_arg_1, 1); break;
    case 2: deps->sort(sort_dep_arg_2, 2); break;
    case 3: deps->sort(sort_dep_arg_3, 3); break;
    case 4: deps->sort(sort_dep_arg_4, 4); break;
    default: ShouldNotReachHere(); break;
    }
  }
}

size_t Dependencies::estimate_size_in_bytes() {
  size_t est_size = 100;
#if INCLUDE_JVMCI
  if (_using_dep_values) {
    for (int deptv = (int)FIRST_TYPE; deptv < (int)TYPE_LIMIT; deptv++) {
      DepType dept = (DepType)deptv;
      GrowableArray<DepValue>* deps = _dep_values[dept];
      est_size += deps->length() * 2;  // tags and argument(s)
    }
    return est_size;
  }
#endif // INCLUDE_JVMCI
  for (int deptv = (int)FIRST_TYPE; deptv < (int)TYPE_LIMIT; deptv++) {
    DepType dept = (DepType)deptv;
    GrowableArray<ciBaseObject*>* deps = _deps[dept];
    est_size += deps->length()*2;  // tags and argument(s)
  }
  return est_size;
}

ciKlass* Dependencies::ctxk_encoded_as_null(DepType dept, ciBaseObject* x) {
  switch (dept) {
  case unique_concrete_method_2:
  case unique_concrete_method_4:
    return x->as_metadata()->as_method()->holder();
  default:
    return nullptr;  // let nullptr be nullptr
  }
}

Klass* Dependencies::ctxk_encoded_as_null(DepType dept, Metadata* x) {
  assert(must_be_in_vm(), "raw oops here");
  switch (dept) {
  case unique_concrete_method_2:
  case unique_concrete_method_4:
    assert(x->is_method(), "sanity");
    return ((Method*)x)->method_holder();
  default:
    return nullptr;  // let nullptr be nullptr
  }
}

void Dependencies::encode_content_bytes() {
  sort_all_deps();

  // cast is safe, no deps can overflow INT_MAX
  CompressedWriteStream bytes((int)estimate_size_in_bytes());

#if INCLUDE_JVMCI
  if (_using_dep_values) {
    for (int deptv = (int)FIRST_TYPE; deptv < (int)TYPE_LIMIT; deptv++) {
      DepType dept = (DepType)deptv;
      GrowableArray<DepValue>* deps = _dep_values[dept];
      if (deps->length() == 0)  continue;
      int stride = dep_args(dept);
      int ctxkj  = dep_context_arg(dept);  // -1 if no context arg
      assert(stride > 0, "sanity");
      for (int i = 0; i < deps->length(); i += stride) {
        jbyte code_byte = (jbyte)dept;
        int skipj = -1;
        if (ctxkj >= 0 && ctxkj+1 < stride) {
          Klass*  ctxk = deps->at(i+ctxkj+0).as_klass(_oop_recorder);
          DepValue x = deps->at(i+ctxkj+1);  // following argument
          if (ctxk == ctxk_encoded_as_null(dept, x.as_metadata(_oop_recorder))) {
            skipj = ctxkj;  // we win:  maybe one less oop to keep track of
            code_byte |= default_context_type_bit;
          }
        }
        bytes.write_byte(code_byte);
        for (int j = 0; j < stride; j++) {
          if (j == skipj)  continue;
          DepValue v = deps->at(i+j);
          int idx = v.index();
          bytes.write_int(idx);
        }
      }
    }
  } else {
#endif // INCLUDE_JVMCI
  for (int deptv = (int)FIRST_TYPE; deptv < (int)TYPE_LIMIT; deptv++) {
    DepType dept = (DepType)deptv;
    GrowableArray<ciBaseObject*>* deps = _deps[dept];
    if (deps->length() == 0)  continue;
    int stride = dep_args(dept);
    int ctxkj  = dep_context_arg(dept);  // -1 if no context arg
    assert(stride > 0, "sanity");
    for (int i = 0; i < deps->length(); i += stride) {
      jbyte code_byte = (jbyte)dept;
      int skipj = -1;
      if (ctxkj >= 0 && ctxkj+1 < stride) {
        ciKlass*  ctxk = deps->at(i+ctxkj+0)->as_metadata()->as_klass();
        ciBaseObject* x     = deps->at(i+ctxkj+1);  // following argument
        if (ctxk == ctxk_encoded_as_null(dept, x)) {
          skipj = ctxkj;  // we win:  maybe one less oop to keep track of
          code_byte |= default_context_type_bit;
        }
      }
      bytes.write_byte(code_byte);
      for (int j = 0; j < stride; j++) {
        if (j == skipj)  continue;
        ciBaseObject* v = deps->at(i+j);
        int idx;
        if (v->is_object()) {
          idx = _oop_recorder->find_index(v->as_object()->constant_encoding());
        } else {
          ciMetadata* meta = v->as_metadata();
          idx = _oop_recorder->find_index(meta->constant_encoding());
        }
        bytes.write_int(idx);
      }
    }
  }
#if INCLUDE_JVMCI
  }
#endif

  // write a sentinel byte to mark the end
  bytes.write_byte(end_marker);

  // round it out to a word boundary
  while (bytes.position() % sizeof(HeapWord) != 0) {
    bytes.write_byte(end_marker);
  }

  // check whether the dept byte encoding really works
  assert((jbyte)default_context_type_bit != 0, "byte overflow");

  _content_bytes = bytes.buffer();
  _size_in_bytes = bytes.position();
}


const char* Dependencies::_dep_name[TYPE_LIMIT] = {
  "end_marker",
  "evol_method",
  "leaf_type",
  "abstract_with_unique_concrete_subtype",
  "unique_concrete_method_2",
  "unique_concrete_method_4",
  "unique_implementor",
  "no_finalizable_subclasses",
  "call_site_target_value"
};

int Dependencies::_dep_args[TYPE_LIMIT] = {
  -1,// end_marker
  1, // evol_method m
  1, // leaf_type ctxk
  2, // abstract_with_unique_concrete_subtype ctxk, k
  2, // unique_concrete_method_2 ctxk, m
  4, // unique_concrete_method_4 ctxk, m, resolved_klass, resolved_method
  2, // unique_implementor ctxk, implementor
  1, // no_finalizable_subclasses ctxk
  2  // call_site_target_value call_site, method_handle
};

const char* Dependencies::dep_name(Dependencies::DepType dept) {
  if (!dept_in_mask(dept, all_types))  return "?bad-dep?";
  return _dep_name[dept];
}

int Dependencies::dep_args(Dependencies::DepType dept) {
  if (!dept_in_mask(dept, all_types))  return -1;
  return _dep_args[dept];
}

void Dependencies::check_valid_dependency_type(DepType dept) {
  guarantee(FIRST_TYPE <= dept && dept < TYPE_LIMIT, "invalid dependency type: %d", (int) dept);
}

Dependencies::DepType Dependencies::validate_dependencies(CompileTask* task, char** failure_detail) {
  int klass_violations = 0;
  DepType result = end_marker;
  for (Dependencies::DepStream deps(this); deps.next(); ) {
    Klass* witness = deps.check_dependency();
    if (witness != nullptr) {
      if (klass_violations == 0) {
        result = deps.type();
        if (failure_detail != nullptr && klass_violations == 0) {
          // Use a fixed size buffer to prevent the string stream from
          // resizing in the context of an inner resource mark.
          char* buffer = NEW_RESOURCE_ARRAY(char, O_BUFLEN);
          stringStream st(buffer, O_BUFLEN);
          deps.print_dependency(&st, witness, true);
          *failure_detail = st.as_string();
        }
      }
      klass_violations++;
      if (xtty == nullptr) {
        // If we're not logging then a single violation is sufficient,
        // otherwise we want to log all the dependences which were
        // violated.
        break;
      }
    }
  }

  return result;
}

// for the sake of the compiler log, print out current dependencies:
void Dependencies::log_all_dependencies() {
  if (log() == nullptr)  return;
  ResourceMark rm;
  for (int deptv = (int)FIRST_TYPE; deptv < (int)TYPE_LIMIT; deptv++) {
    DepType dept = (DepType)deptv;
    GrowableArray<ciBaseObject*>* deps = _deps[dept];
    int deplen = deps->length();
    if (deplen == 0) {
      continue;
    }
    int stride = dep_args(dept);
    GrowableArray<ciBaseObject*>* ciargs = new GrowableArray<ciBaseObject*>(stride);
    for (int i = 0; i < deps->length(); i += stride) {
      for (int j = 0; j < stride; j++) {
        // flush out the identities before printing
        ciargs->push(deps->at(i+j));
      }
      write_dependency_to(log(), dept, ciargs);
      ciargs->clear();
    }
    guarantee(deplen == deps->length(), "deps array cannot grow inside nested ResoureMark scope");
  }
}

void Dependencies::write_dependency_to(CompileLog* log,
                                       DepType dept,
                                       GrowableArray<DepArgument>* args,
                                       Klass* witness) {
  if (log == nullptr) {
    return;
  }
  ResourceMark rm;
  ciEnv* env = ciEnv::current();
  GrowableArray<ciBaseObject*>* ciargs = new GrowableArray<ciBaseObject*>(args->length());
  for (GrowableArrayIterator<DepArgument> it = args->begin(); it != args->end(); ++it) {
    DepArgument arg = *it;
    if (arg.is_oop()) {
      ciargs->push(env->get_object(arg.oop_value()));
    } else {
      ciargs->push(env->get_metadata(arg.metadata_value()));
    }
  }
  int argslen = ciargs->length();
  Dependencies::write_dependency_to(log, dept, ciargs, witness);
  guarantee(argslen == ciargs->length(), "ciargs array cannot grow inside nested ResoureMark scope");
}

void Dependencies::write_dependency_to(CompileLog* log,
                                       DepType dept,
                                       GrowableArray<ciBaseObject*>* args,
                                       Klass* witness) {
  if (log == nullptr) {
    return;
  }
  ResourceMark rm;
  GrowableArray<int>* argids = new GrowableArray<int>(args->length());
  for (GrowableArrayIterator<ciBaseObject*> it = args->begin(); it != args->end(); ++it) {
    ciBaseObject* obj = *it;
    if (obj->is_object()) {
      argids->push(log->identify(obj->as_object()));
    } else {
      argids->push(log->identify(obj->as_metadata()));
    }
  }
  if (witness != nullptr) {
    log->begin_elem("dependency_failed");
  } else {
    log->begin_elem("dependency");
  }
  log->print(" type='%s'", dep_name(dept));
  const int ctxkj = dep_context_arg(dept);  // -1 if no context arg
  if (ctxkj >= 0 && ctxkj < argids->length()) {
    log->print(" ctxk='%d'", argids->at(ctxkj));
  }
  // write remaining arguments, if any.
  for (int j = 0; j < argids->length(); j++) {
    if (j == ctxkj)  continue;  // already logged
    if (j == 1) {
      log->print(  " x='%d'",    argids->at(j));
    } else {
      log->print(" x%d='%d'", j, argids->at(j));
    }
  }
  if (witness != nullptr) {
    log->object("witness", witness);
    log->stamp();
  }
  log->end_elem();
}

void Dependencies::write_dependency_to(xmlStream* xtty,
                                       DepType dept,
                                       GrowableArray<DepArgument>* args,
                                       Klass* witness) {
  if (xtty == nullptr) {
    return;
  }
  Thread* thread = Thread::current();
  HandleMark rm(thread);
  ttyLocker ttyl;
  int ctxkj = dep_context_arg(dept);  // -1 if no context arg
  if (witness != nullptr) {
    xtty->begin_elem("dependency_failed");
  } else {
    xtty->begin_elem("dependency");
  }
  xtty->print(" type='%s'", dep_name(dept));
  if (ctxkj >= 0) {
    xtty->object("ctxk", args->at(ctxkj).metadata_value());
  }
  // write remaining arguments, if any.
  for (int j = 0; j < args->length(); j++) {
    if (j == ctxkj)  continue;  // already logged
    DepArgument arg = args->at(j);
    if (j == 1) {
      if (arg.is_oop()) {
        xtty->object("x", Handle(thread, arg.oop_value()));
      } else {
        xtty->object("x", arg.metadata_value());
      }
    } else {
      char xn[12];
      os::snprintf_checked(xn, sizeof(xn), "x%d", j);
      if (arg.is_oop()) {
        xtty->object(xn, Handle(thread, arg.oop_value()));
      } else {
        xtty->object(xn, arg.metadata_value());
      }
    }
  }
  if (witness != nullptr) {
    xtty->object("witness", witness);
    xtty->stamp();
  }
  xtty->end_elem();
}

void Dependencies::print_dependency(DepType dept, GrowableArray<DepArgument>* args,
                                    Klass* witness, outputStream* st) {
  ResourceMark rm;
  ttyLocker ttyl;   // keep the following output all in one block
  st->print_cr("%s of type %s",
                (witness == nullptr)? "Dependency": "Failed dependency",
                dep_name(dept));
  // print arguments
  int ctxkj = dep_context_arg(dept);  // -1 if no context arg
  for (int j = 0; j < args->length(); j++) {
    DepArgument arg = args->at(j);
    bool put_star = false;
    if (arg.is_null())  continue;
    const char* what;
    if (j == ctxkj) {
      assert(arg.is_metadata(), "must be");
      what = "context";
      put_star = !Dependencies::is_concrete_klass((Klass*)arg.metadata_value());
    } else if (arg.is_method()) {
      what = "method ";
      put_star = !Dependencies::is_concrete_method((Method*)arg.metadata_value(), nullptr);
    } else if (arg.is_klass()) {
      what = "class  ";
    } else {
      what = "object ";
    }
    st->print("  %s = %s", what, (put_star? "*": ""));
    if (arg.is_klass()) {
      st->print("%s", ((Klass*)arg.metadata_value())->external_name());
    } else if (arg.is_method()) {
      ((Method*)arg.metadata_value())->print_value_on(st);
    } else if (arg.is_oop()) {
      arg.oop_value()->print_value_on(st);
    } else {
      ShouldNotReachHere(); // Provide impl for this type.
    }

    st->cr();
  }
  if (witness != nullptr) {
    bool put_star = !Dependencies::is_concrete_klass(witness);
    st->print_cr("  witness = %s%s",
                  (put_star? "*": ""),
                  witness->external_name());
  }
}

void Dependencies::DepStream::log_dependency(Klass* witness) {
  if (_deps == nullptr && xtty == nullptr)  return;  // fast cutout for runtime
  ResourceMark rm;
  const int nargs = argument_count();
  GrowableArray<DepArgument>* args = new GrowableArray<DepArgument>(nargs);
  for (int j = 0; j < nargs; j++) {
    if (is_oop_argument(j)) {
      args->push(argument_oop(j));
    } else {
      args->push(argument(j));
    }
  }
  int argslen = args->length();
  if (_deps != nullptr && _deps->log() != nullptr) {
    if (ciEnv::current() != nullptr) {
      Dependencies::write_dependency_to(_deps->log(), type(), args, witness);
    } else {
      // Treat the CompileLog as an xmlstream instead
      Dependencies::write_dependency_to((xmlStream*)_deps->log(), type(), args, witness);
    }
  } else {
    Dependencies::write_dependency_to(xtty, type(), args, witness);
  }
  guarantee(argslen == args->length(), "args array cannot grow inside nested ResoureMark scope");
}

void Dependencies::DepStream::print_dependency(outputStream* st, Klass* witness, bool verbose) {
  ResourceMark rm;
  int nargs = argument_count();
  GrowableArray<DepArgument>* args = new GrowableArray<DepArgument>(nargs);
  for (int j = 0; j < nargs; j++) {
    if (is_oop_argument(j)) {
      args->push(argument_oop(j));
    } else {
      args->push(argument(j));
    }
  }
  int argslen = args->length();
  Dependencies::print_dependency(type(), args, witness, st);
  if (verbose) {
    if (_code != nullptr) {
      st->print("  code: ");
      _code->print_value_on(st);
      st->cr();
    }
  }
  guarantee(argslen == args->length(), "args array cannot grow inside nested ResoureMark scope");
}


/// Dependency stream support (decodes dependencies from an nmethod):

#ifdef ASSERT
void Dependencies::DepStream::initial_asserts(size_t byte_limit) {
  assert(must_be_in_vm(), "raw oops here");
  _byte_limit = byte_limit;
  _type       = undefined_dependency;  // defeat "already at end" assert
  assert((_code!=nullptr) + (_deps!=nullptr) == 1, "one or t'other");
}
#endif //ASSERT

bool Dependencies::DepStream::next() {
  assert(_type != end_marker, "already at end");
  if (_bytes.position() == 0 && _code != nullptr
      && _code->dependencies_size() == 0) {
    // Method has no dependencies at all.
    return false;
  }
  int code_byte = (_bytes.read_byte() & 0xFF);
  if (code_byte == end_marker) {
    DEBUG_ONLY(_type = end_marker);
    return false;
  } else {
    int ctxk_bit = (code_byte & Dependencies::default_context_type_bit);
    code_byte -= ctxk_bit;
    DepType dept = (DepType)code_byte;
    _type = dept;
    Dependencies::check_valid_dependency_type(dept);
    int stride = _dep_args[dept];
    assert(stride == dep_args(dept), "sanity");
    int skipj = -1;
    if (ctxk_bit != 0) {
      skipj = 0;  // currently the only context argument is at zero
      assert(skipj == dep_context_arg(dept), "zero arg always ctxk");
    }
    for (int j = 0; j < stride; j++) {
      _xi[j] = (j == skipj)? 0: _bytes.read_int();
    }
    DEBUG_ONLY(_xi[stride] = -1);   // help detect overruns
    return true;
  }
}

inline Metadata* Dependencies::DepStream::recorded_metadata_at(int i) {
  Metadata* o = nullptr;
  if (_code != nullptr) {
    o = _code->metadata_at(i);
  } else {
    o = _deps->oop_recorder()->metadata_at(i);
  }
  return o;
}

inline oop Dependencies::DepStream::recorded_oop_at(int i) {
  return (_code != nullptr)
         ? _code->oop_at(i)
    : JNIHandles::resolve(_deps->oop_recorder()->oop_at(i));
}

Metadata* Dependencies::DepStream::argument(int i) {
  Metadata* result = recorded_metadata_at(argument_index(i));

  if (result == nullptr) { // Explicit context argument can be compressed
    int ctxkj = dep_context_arg(type());  // -1 if no explicit context arg
    if (ctxkj >= 0 && i == ctxkj && ctxkj+1 < argument_count()) {
      result = ctxk_encoded_as_null(type(), argument(ctxkj+1));
    }
  }

  assert(result == nullptr || result->is_klass() || result->is_method(), "must be");
  return result;
}

/**
 * Returns a unique identifier for each dependency argument.
 */
uintptr_t Dependencies::DepStream::get_identifier(int i) {
  if (is_oop_argument(i)) {
    return (uintptr_t)(oopDesc*)argument_oop(i);
  } else {
    return (uintptr_t)argument(i);
  }
}

oop Dependencies::DepStream::argument_oop(int i) {
  oop result = recorded_oop_at(argument_index(i));
  assert(oopDesc::is_oop_or_null(result), "must be");
  return result;
}

InstanceKlass* Dependencies::DepStream::context_type() {
  assert(must_be_in_vm(), "raw oops here");

  // Most dependencies have an explicit context type argument.
  {
    int ctxkj = dep_context_arg(type());  // -1 if no explicit context arg
    if (ctxkj >= 0) {
      Metadata* k = argument(ctxkj);
      assert(k != nullptr && k->is_klass(), "type check");
      return InstanceKlass::cast((Klass*)k);
    }
  }

  // Some dependencies are using the klass of the first object
  // argument as implicit context type.
  {
    int ctxkj = dep_implicit_context_arg(type());
    if (ctxkj >= 0) {
      Klass* k = argument_oop(ctxkj)->klass();
      assert(k != nullptr, "type check");
      return InstanceKlass::cast(k);
    }