/*

 * Copyright (c) 2005, 2013, 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 "code/dependencies.hpp"

#include "compiler/compileLog.hpp"

#include "oops/oop.inline.hpp"

#include "runtime/handles.hpp"

#include "runtime/handles.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);

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

  check_ctxk(call_site->klass());

  assert_common_2(call_site_target_value, call_site, method_handle);

}

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

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

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

}

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

void Dependencies::sort_all_deps() {

  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;

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

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

      }

    }

  }

  // 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",

  "abstract_with_no_concrete_subtype",

  "concrete_with_no_concrete_subtype",

  "unique_concrete_method",

  "abstract_with_exclusive_concrete_subtypes_2",

  "exclusive_concrete_methods_2",

  "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

  1, // abstract_with_no_concrete_subtype ctxk

  1, // concrete_with_no_concrete_subtype ctxk

  2, // unique_concrete_method ctxk, m

  3, // unique_concrete_subtypes_2 ctxk, k1, k2

  3, // unique_concrete_methods_2 ctxk, m1, m2

  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, err_msg("invalid dependency type: %d", (int) dept));

}

// for the sake of the compiler log, print out current dependencies:

void Dependencies::log_all_dependencies() {

  if (log() == NULL)  return;

  ciBaseObject* args[max_arg_count];

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

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

      for (int j = 0; j < stride; j++) {

        // flush out the identities before printing

        args[j] = deps->at(i+j);

      }

      write_dependency_to(log(), dept, stride, args);

    }

  }

}

void Dependencies::write_dependency_to(CompileLog* log,

                                       DepType dept,

                                       int nargs, DepArgument args[],

                                       Klass* witness) {

  if (log == NULL) {

    return;

  }

  ciEnv* env = ciEnv::current();

  ciBaseObject* ciargs[max_arg_count];

  assert(nargs <= max_arg_count, "oob");

  for (int j = 0; j < nargs; j++) {

    if (args[j].is_oop()) {

      ciargs[j] = env->get_object(args[j].oop_value());

    } else {

      ciargs[j] = env->get_metadata(args[j].metadata_value());

    }

  }

  Dependencies::write_dependency_to(log, dept, nargs, ciargs, witness);

}

void Dependencies::write_dependency_to(CompileLog* log,

                                       DepType dept,

                                       int nargs, ciBaseObject* args[],

                                       Klass* witness) {

  if (log == NULL)  return;

  assert(nargs <= max_arg_count, "oob");

  int argids[max_arg_count];

  int ctxkj = dep_context_arg(dept);  // -1 if no context arg

  int j;

  for (j = 0; j < nargs; j++) {

    if (args[j]->is_object()) {

      argids[j] = log->identify(args[j]->as_object());

    } else {

      argids[j] = log->identify(args[j]->as_metadata());

    }

  }

  if (witness != NULL) {

    log->begin_elem("dependency_failed");

  } else {

    log->begin_elem("dependency");

  }

  log->print(" type='%s'", dep_name(dept));

  if (ctxkj >= 0) {

    log->print(" ctxk='%d'", argids[ctxkj]);

  }

  // write remaining arguments, if any.

  for (j = 0; j < nargs; j++) {

    if (j == ctxkj)  continue;  // already logged

    if (j == 1) {

      log->print(  " x='%d'",    argids[j]);

    } else {

      log->print(" x%d='%d'", j, argids[j]);

    }

  }

  if (witness != NULL) {

    log->object("witness", witness);

    log->stamp();

  }

  log->end_elem();

}

void Dependencies::write_dependency_to(xmlStream* xtty,

                                       DepType dept,

                                       int nargs, DepArgument args[],

                                       Klass* witness) {

  if (xtty == NULL)  return;

  ttyLocker ttyl;

  int ctxkj = dep_context_arg(dept);  // -1 if no context arg

  if (witness != NULL) {

    xtty->begin_elem("dependency_failed");

  } else {

    xtty->begin_elem("dependency");

  }

  xtty->print(" type='%s'", dep_name(dept));

  if (ctxkj >= 0) {

    xtty->object("ctxk", args[ctxkj].metadata_value());

  }

  // write remaining arguments, if any.

  for (int j = 0; j < nargs; j++) {

    if (j == ctxkj)  continue;  // already logged

    if (j == 1) {

      if (args[j].is_oop()) {

        xtty->object("x", args[j].oop_value());

      } else {

        xtty->object("x", args[j].metadata_value());

      }

    } else {

      char xn[10]; sprintf(xn, "x%d", j);

      if (args[j].is_oop()) {