/*

 * Copyright (c) 2005, 2015, 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 "precompiled.hpp"

#include "ci/ciArrayKlass.hpp"

#include "ci/ciEnv.hpp"

#include "ci/ciKlass.hpp"

#include "ci/ciMethod.hpp"

#include "classfile/javaClasses.inline.hpp"

#include "code/dependencies.hpp"

#include "compiler/compileLog.hpp"

#include "oops/oop.inline.hpp"

#include "oops/objArrayKlass.hpp"

#include "runtime/handles.hpp"

#include "runtime/handles.inline.hpp"

#include "runtime/thread.inline.hpp"

#include "utilities/copy.hpp"

#ifdef ASSERT

static bool must_be_in_vm() {

  Thread* thread = Thread::current();

  if (thread->is_Java_thread())

    return ((JavaThread*)thread)->thread_state() == _thread_in_vm;

  else

    return true;  //something like this: thread->is_VM_thread();

}

#endif //ASSERT

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] = NULL);

  for (int i = (int)FIRST_TYPE; i < (int)TYPE_LIMIT; i++) {

    _deps[i] = new(arena) GrowableArray<ciBaseObject*>(arena, 10, 0, 0);

  }

  _content_bytes = NULL;

  _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_abstract_with_no_concrete_subtype(ciKlass* ctxk) {

  check_ctxk_abstract(ctxk);

  assert_common_1(abstract_with_no_concrete_subtype, ctxk);

}

void Dependencies::assert_concrete_with_no_concrete_subtype(ciKlass* ctxk) {

  check_ctxk_concrete(ctxk);

  assert_common_1(concrete_with_no_concrete_subtype, ctxk);

}

void Dependencies::assert_unique_concrete_method(ciKlass* ctxk, ciMethod* uniqm) {

  check_ctxk(ctxk);

  assert_common_2(unique_concrete_method, ctxk, uniqm);

}

void Dependencies::assert_abstract_with_exclusive_concrete_subtypes(ciKlass* ctxk, ciKlass* k1, ciKlass* k2) {

  check_ctxk(ctxk);

  assert_common_3(abstract_with_exclusive_concrete_subtypes_2, ctxk, k1, k2);

}

void Dependencies::assert_exclusive_concrete_methods(ciKlass* ctxk, ciMethod* m1, ciMethod* m2) {

  check_ctxk(ctxk);

  assert_common_3(exclusive_concrete_methods_2, ctxk, m1, m2);

}

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] = NULL);

  for (int i = (int)FIRST_TYPE; i < (int)TYPE_LIMIT; i++) {

    _dep_values[i] = new(arena) GrowableArray<DepValue>(arena, 10, 0, DepValue());

  }

  _content_bytes = NULL;

  _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->oop_is_array()) {

    // 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_concrete_method(Klass* ctxk, Method* uniqm) {

  check_ctxk(ctxk);

  assert_common_2(unique_concrete_method, 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 {

    if (note_dep_seen(dept, x0) && 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* 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_3(DepType dept,

                                   ciKlass* ctxk, ciBaseObject* x, ciBaseObject* x2) {

  assert(dep_context_arg(dept) == 0, "sanity");

  assert(dep_args(dept) == 3, "sanity");

  log_dependency(dept, ctxk, x, x2);

  GrowableArray<ciBaseObject*>* deps = _deps[dept];

  // try to normalize an unordered pair:

  bool swap = false;

  switch (dept) {

  case abstract_with_exclusive_concrete_subtypes_2:

    swap = (x->ident() > x2->ident() && x->as_metadata()->as_klass() != ctxk);

    break;

  case exclusive_concrete_methods_2:

    swap = (x->ident() > x2->ident() && x->as_metadata()->as_method()->holder() != ctxk);

    break;

  }

  if (swap) { ciBaseObject* t = x; x = x2; x2 = t; }

  // see if the same (or a similar) dep is already recorded

  if (note_dep_seen(dept, x) && note_dep_seen(dept, x2)) {

    // look in this bucket for redundant assertions

    const int stride = 3;

    for (int i = deps->length(); (i -= stride) >= 0; ) {

      ciBaseObject* y  = deps->at(i+1);

      ciBaseObject* y2 = deps->at(i+2);

      if (x == y && x2 == y2) {  // 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(x);

  deps->append(x2);

}

#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 {

    assert(dep_implicit_context_arg(dept) == 0, "sanity");

    if (note_dep_seen(dept, x0) && 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 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");

  Copy::disjoint_words((HeapWord*) content_bytes(),

                       (HeapWord*) beg,

                       size_in_bytes() / sizeof(HeapWord));

  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); }

#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();

      }

    }

    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;

    default: ShouldNotReachHere();

    }

  }

}

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 abstract_with_exclusive_concrete_subtypes_2:

    return x->as_metadata()->as_klass();

  case unique_concrete_method:

  case exclusive_concrete_methods_2:

    return x->as_metadata()->as_method()->holder();

  }

  return NULL;  // let NULL be NULL

}

Klass* Dependencies::ctxk_encoded_as_null(DepType dept, Metadata* x) {

  assert(must_be_in_vm(), "raw oops here");

  switch (dept) {

  case abstract_with_exclusive_concrete_subtypes_2:

    assert(x->is_klass(), "sanity");

    return (Klass*) x;

  case unique_concrete_method:

  case exclusive_concrete_methods_2:

    assert(x->is_method(), "sanity");

    return ((Method*)x)->method_holder();

  }

  return NULL;  // let NULL be NULL

}

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) {