/*

 * Copyright (c) 1998, 2018, 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/ciMethodData.hpp"

#include "classfile/systemDictionary.hpp"

#include "classfile/vmSymbols.hpp"

#include "compiler/compileLog.hpp"

#include "interpreter/linkResolver.hpp"

#include "memory/resourceArea.hpp"

#include "memory/universe.hpp"

#include "oops/oop.inline.hpp"

#include "opto/addnode.hpp"

#include "opto/castnode.hpp"

#include "opto/convertnode.hpp"

#include "opto/divnode.hpp"

#include "opto/idealGraphPrinter.hpp"

#include "opto/matcher.hpp"

#include "opto/memnode.hpp"

#include "opto/mulnode.hpp"

#include "opto/opaquenode.hpp"

#include "opto/parse.hpp"

#include "opto/runtime.hpp"

#include "runtime/deoptimization.hpp"

#include "runtime/sharedRuntime.hpp"

#ifndef PRODUCT

extern int explicit_null_checks_inserted,

           explicit_null_checks_elided;

#endif

//---------------------------------array_load----------------------------------

void Parse::array_load(BasicType bt) {

  const Type* elemtype = Type::TOP;

  bool big_val = bt == T_DOUBLE || bt == T_LONG;

  Node* adr = array_addressing(bt, 0, &elemtype);

  if (stopped())  return;     // guaranteed null or range check

  pop();                      // index (already used)

  Node* array = pop();        // the array itself

  if (elemtype == TypeInt::BOOL) {

    bt = T_BOOLEAN;

  } else if (bt == T_OBJECT) {

    elemtype = _gvn.type(array)->is_aryptr()->elem()->make_oopptr();

  }

  const TypeAryPtr* adr_type = TypeAryPtr::get_array_body_type(bt);

  Node* ld = access_load_at(array, adr, adr_type, elemtype, bt,

                            IN_HEAP | IS_ARRAY | C2_CONTROL_DEPENDENT_LOAD);

  if (big_val) {

    push_pair(ld);

  } else {

    push(ld);

  }

}

//--------------------------------array_store----------------------------------

void Parse::array_store(BasicType bt) {

  const Type* elemtype = Type::TOP;

  bool big_val = bt == T_DOUBLE || bt == T_LONG;

  Node* adr = array_addressing(bt, big_val ? 2 : 1, &elemtype);

  if (stopped())  return;     // guaranteed null or range check

  if (bt == T_OBJECT) {

    array_store_check();

  }

  Node* val;                  // Oop to store

  if (big_val) {

    val = pop_pair();

  } else {

    val = pop();

  }

  pop();                      // index (already used)

  Node* array = pop();        // the array itself

  if (elemtype == TypeInt::BOOL) {

    bt = T_BOOLEAN;

  } else if (bt == T_OBJECT) {

    elemtype = _gvn.type(array)->is_aryptr()->elem()->make_oopptr();

  }

  const TypeAryPtr* adr_type = TypeAryPtr::get_array_body_type(bt);

  access_store_at(array, adr, adr_type, val, elemtype, bt, MO_UNORDERED | IN_HEAP | IS_ARRAY);

}

//------------------------------array_addressing-------------------------------

// Pull array and index from the stack.  Compute pointer-to-element.

Node* Parse::array_addressing(BasicType type, int vals, const Type* *result2) {

  Node *idx   = peek(0+vals);   // Get from stack without popping

  Node *ary   = peek(1+vals);   // in case of exception

  // Null check the array base, with correct stack contents

  ary = null_check(ary, T_ARRAY);

  // Compile-time detect of null-exception?

  if (stopped())  return top();

  const TypeAryPtr* arytype  = _gvn.type(ary)->is_aryptr();

  const TypeInt*    sizetype = arytype->size();

  const Type*       elemtype = arytype->elem();

  if (UseUniqueSubclasses && result2 != NULL) {

    const Type* el = elemtype->make_ptr();

    if (el && el->isa_instptr()) {

      const TypeInstPtr* toop = el->is_instptr();

      if (toop->klass()->as_instance_klass()->unique_concrete_subklass()) {

        // If we load from "AbstractClass[]" we must see "ConcreteSubClass".

        const Type* subklass = Type::get_const_type(toop->klass());

        elemtype = subklass->join_speculative(el);

      }

    }

  }

  // Check for big class initializers with all constant offsets

  // feeding into a known-size array.

  const TypeInt* idxtype = _gvn.type(idx)->is_int();

  // See if the highest idx value is less than the lowest array bound,

  // and if the idx value cannot be negative:

  bool need_range_check = true;

  if (idxtype->_hi < sizetype->_lo && idxtype->_lo >= 0) {

    need_range_check = false;

    if (C->log() != NULL)   C->log()->elem("observe that='!need_range_check'");

  }

  ciKlass * arytype_klass = arytype->klass();

  if ((arytype_klass != NULL) && (!arytype_klass->is_loaded())) {

    // Only fails for some -Xcomp runs

    // The class is unloaded.  We have to run this bytecode in the interpreter.

    uncommon_trap(Deoptimization::Reason_unloaded,

                  Deoptimization::Action_reinterpret,

                  arytype->klass(), "!loaded array");

    return top();

  }

  // Do the range check

  if (GenerateRangeChecks && need_range_check) {

    Node* tst;

    if (sizetype->_hi <= 0) {

      // The greatest array bound is negative, so we can conclude that we're

      // compiling unreachable code, but the unsigned compare trick used below

      // only works with non-negative lengths.  Instead, hack "tst" to be zero so

      // the uncommon_trap path will always be taken.

      tst = _gvn.intcon(0);

    } else {

      // Range is constant in array-oop, so we can use the original state of mem

      Node* len = load_array_length(ary);

      // Test length vs index (standard trick using unsigned compare)

      Node* chk = _gvn.transform( new CmpUNode(idx, len) );

      BoolTest::mask btest = BoolTest::lt;

      tst = _gvn.transform( new BoolNode(chk, btest) );

    }

    RangeCheckNode* rc = new RangeCheckNode(control(), tst, PROB_MAX, COUNT_UNKNOWN);

    _gvn.set_type(rc, rc->Value(&_gvn));

    if (!tst->is_Con()) {

      record_for_igvn(rc);

    }

    set_control(_gvn.transform(new IfTrueNode(rc)));

    // Branch to failure if out of bounds

    {

      PreserveJVMState pjvms(this);

      set_control(_gvn.transform(new IfFalseNode(rc)));

      if (C->allow_range_check_smearing()) {

        // Do not use builtin_throw, since range checks are sometimes

        // made more stringent by an optimistic transformation.

        // This creates "tentative" range checks at this point,

        // which are not guaranteed to throw exceptions.

        // See IfNode::Ideal, is_range_check, adjust_check.

        uncommon_trap(Deoptimization::Reason_range_check,

                      Deoptimization::Action_make_not_entrant,

                      NULL, "range_check");

      } else {

        // If we have already recompiled with the range-check-widening

        // heroic optimization turned off, then we must really be throwing

        // range check exceptions.

        builtin_throw(Deoptimization::Reason_range_check, idx);

      }

    }

  }

  // Check for always knowing you are throwing a range-check exception

  if (stopped())  return top();

  // Make array address computation control dependent to prevent it

  // from floating above the range check during loop optimizations.

  Node* ptr = array_element_address(ary, idx, type, sizetype, control());

  if (result2 != NULL)  *result2 = elemtype;

  assert(ptr != top(), "top should go hand-in-hand with stopped");

  return ptr;

}

// returns IfNode

IfNode* Parse::jump_if_fork_int(Node* a, Node* b, BoolTest::mask mask, float prob, float cnt) {

  Node   *cmp = _gvn.transform(new CmpINode(a, b)); // two cases: shiftcount > 32 and shiftcount <= 32

  Node   *tst = _gvn.transform(new BoolNode(cmp, mask));

  IfNode *iff = create_and_map_if(control(), tst, prob, cnt);

  return iff;

}

// return Region node

Node* Parse::jump_if_join(Node* iffalse, Node* iftrue) {

  Node *region  = new RegionNode(3); // 2 results

  record_for_igvn(region);

  region->init_req(1, iffalse);

  region->init_req(2, iftrue );

  _gvn.set_type(region, Type::CONTROL);

  region = _gvn.transform(region);

  set_control (region);

  return region;

}

// sentinel value for the target bci to mark never taken branches

// (according to profiling)

static const int never_reached = INT_MAX;

//------------------------------helper for tableswitch-------------------------

void Parse::jump_if_true_fork(IfNode *iff, int dest_bci_if_true, int prof_table_index, bool unc) {

  // True branch, use existing map info

  { PreserveJVMState pjvms(this);

    Node *iftrue  = _gvn.transform( new IfTrueNode (iff) );

    set_control( iftrue );

    if (unc) {

      repush_if_args();

      uncommon_trap(Deoptimization::Reason_unstable_if,

                    Deoptimization::Action_reinterpret,

                    NULL,

                    "taken always");

    } else {

      assert(dest_bci_if_true != never_reached, "inconsistent dest");

      profile_switch_case(prof_table_index);

      merge_new_path(dest_bci_if_true);

    }

  }

  // False branch

  Node *iffalse = _gvn.transform( new IfFalseNode(iff) );

  set_control( iffalse );

}

void Parse::jump_if_false_fork(IfNode *iff, int dest_bci_if_true, int prof_table_index, bool unc) {

  // True branch, use existing map info

  { PreserveJVMState pjvms(this);

    Node *iffalse  = _gvn.transform( new IfFalseNode (iff) );

    set_control( iffalse );

    if (unc) {

      repush_if_args();

      uncommon_trap(Deoptimization::Reason_unstable_if,

                    Deoptimization::Action_reinterpret,

                    NULL,

                    "taken never");

    } else {

      assert(dest_bci_if_true != never_reached, "inconsistent dest");

      profile_switch_case(prof_table_index);

      merge_new_path(dest_bci_if_true);

    }

  }

  // False branch

  Node *iftrue = _gvn.transform( new IfTrueNode(iff) );

  set_control( iftrue );

}

void Parse::jump_if_always_fork(int dest_bci, int prof_table_index, bool unc) {

  // False branch, use existing map and control()

  if (unc) {

    repush_if_args();

    uncommon_trap(Deoptimization::Reason_unstable_if,

                  Deoptimization::Action_reinterpret,

                  NULL,

                  "taken never");

  } else {

    assert(dest_bci != never_reached, "inconsistent dest");

    profile_switch_case(prof_table_index);

    merge_new_path(dest_bci);

  }

}

extern "C" {

  static int jint_cmp(const void *i, const void *j) {

    int a = *(jint *)i;

    int b = *(jint *)j;

    return a > b ? 1 : a < b ? -1 : 0;

  }

}

// Default value for methodData switch indexing. Must be a negative value to avoid

// conflict with any legal switch index.

#define NullTableIndex -1

class SwitchRange : public StackObj {

  // a range of integers coupled with a bci destination

  jint _lo;                     // inclusive lower limit

  jint _hi;                     // inclusive upper limit

  int _dest;

  int _table_index;             // index into method data table

  float _cnt;                   // how many times this range was hit according to profiling

public:

  jint lo() const              { return _lo;   }

  jint hi() const              { return _hi;   }

  int  dest() const            { return _dest; }

  int  table_index() const     { return _table_index; }

  bool is_singleton() const    { return _lo == _hi; }

  float cnt() const            { return _cnt; }

  void setRange(jint lo, jint hi, int dest, int table_index, float cnt) {

    assert(lo <= hi, "must be a non-empty range");

    _lo = lo, _hi = hi; _dest = dest; _table_index = table_index; _cnt = cnt;

    assert(_cnt >= 0, "");

  }

  bool adjoinRange(jint lo, jint hi, int dest, int table_index, float cnt, bool trim_ranges) {

    assert(lo <= hi, "must be a non-empty range");

    if (lo == _hi+1 && table_index == _table_index) {

      // see merge_ranges() comment below

      if (trim_ranges) {

        if (cnt == 0) {

          if (_cnt != 0) {

            return false;

          }

          if (dest != _dest) {

            _dest = never_reached;

          }

        } else {

          if (_cnt == 0) {

            return false;

          }

          if (dest != _dest) {

            return false;

          }

        }

      } else {

        if (dest != _dest) {

          return false;

        }

      }

      _hi = hi;

      _cnt += cnt;

      return true;

    }

    return false;

  }

  void set (jint value, int dest, int table_index, float cnt) {

    setRange(value, value, dest, table_index, cnt);

  }

  bool adjoin(jint value, int dest, int table_index, float cnt, bool trim_ranges) {

    return adjoinRange(value, value, dest, table_index, cnt, trim_ranges);

  }

  bool adjoin(SwitchRange& other) {

    return adjoinRange(other._lo, other._hi, other._dest, other._table_index, other._cnt, false);

  }

  void print() {

    if (is_singleton())

      tty->print(" {%d}=>%d (cnt=%f)", lo(), dest(), cnt());

    else if (lo() == min_jint)

      tty->print(" {..%d}=>%d (cnt=%f)", hi(), dest(), cnt());

    else if (hi() == max_jint)

      tty->print(" {%d..}=>%d (cnt=%f)", lo(), dest(), cnt());

    else

      tty->print(" {%d..%d}=>%d (cnt=%f)", lo(), hi(), dest(), cnt());

  }

};

// We try to minimize the number of ranges and the size of the taken

// ones using profiling data. When ranges are created,

// SwitchRange::adjoinRange() only allows 2 adjoining ranges to merge

// if both were never hit or both were hit to build longer unreached

// ranges. Here, we now merge adjoining ranges with the same

// destination and finally set destination of unreached ranges to the

// special value never_reached because it can help minimize the number

// of tests that are necessary.

//

// For instance:

// [0, 1] to target1 sometimes taken

// [1, 2] to target1 never taken

// [2, 3] to target2 never taken

// would lead to:

// [0, 1] to target1 sometimes taken

// [1, 3] never taken

//

// (first 2 ranges to target1 are not merged)

static void merge_ranges(SwitchRange* ranges, int& rp) {

  if (rp == 0) {

    return;

  }

  int shift = 0;

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

    SwitchRange& r1 = ranges[j-shift];

    SwitchRange& r2 = ranges[j+1];

    if (r1.adjoin(r2)) {

      shift++;

    } else if (shift > 0) {

      ranges[j+1-shift] = r2;

    }

  }

  rp -= shift;

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

    SwitchRange& r = ranges[j];

    if (r.cnt() == 0 && r.dest() != never_reached) {

      r.setRange(r.lo(), r.hi(), never_reached, r.table_index(), r.cnt());

    }

  }

}

//-------------------------------do_tableswitch--------------------------------

void Parse::do_tableswitch() {

  Node* lookup = pop();

  // Get information about tableswitch

  int default_dest = iter().get_dest_table(0);

  int lo_index     = iter().get_int_table(1);

  int hi_index     = iter().get_int_table(2);

  int len          = hi_index - lo_index + 1;

  if (len < 1) {

    // If this is a backward branch, add safepoint

    maybe_add_safepoint(default_dest);

    merge(default_dest);

    return;

  }

  ciMethodData* methodData = method()->method_data();

  ciMultiBranchData* profile = NULL;

  if (methodData->is_mature() && UseSwitchProfiling) {

    ciProfileData* data = methodData->bci_to_data(bci());

    if (data != NULL && data->is_MultiBranchData()) {

      profile = (ciMultiBranchData*)data;

    }

  }

  bool trim_ranges = !method_data_update() && !C->too_many_traps(method(), bci(), Deoptimization::Reason_unstable_if);

  // generate decision tree, using trichotomy when possible

  int rnum = len+2;

  bool makes_backward_branch = false;

  SwitchRange* ranges = NEW_RESOURCE_ARRAY(SwitchRange, rnum);

  int rp = -1;

  if (lo_index != min_jint) {

    uint cnt = 1;

    if (profile != NULL) {

      cnt = profile->default_count() / (hi_index != max_jint ? 2 : 1);

    }

    ranges[++rp].setRange(min_jint, lo_index-1, default_dest, NullTableIndex, cnt);

  }

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

    jint match_int = lo_index+j;

    int  dest      = iter().get_dest_table(j+3);

    makes_backward_branch |= (dest <= bci());

    int  table_index = method_data_update() ? j : NullTableIndex;

    uint cnt = 1;

    if (profile != NULL) {

      cnt = profile->count_at(j);

    }

    if (rp < 0 || !ranges[rp].adjoin(match_int, dest, table_index, cnt, trim_ranges)) {

      ranges[++rp].set(match_int, dest, table_index, cnt);

    }

  }

  jint highest = lo_index+(len-1);

  assert(ranges[rp].hi() == highest, "");

  if (highest != max_jint) {

    uint cnt = 1;

    if (profile != NULL) {

      cnt = profile->default_count() / (lo_index != min_jint ? 2 : 1);

    }

    if (!ranges[rp].adjoinRange(highest+1, max_jint, default_dest, NullTableIndex, cnt, trim_ranges)) {

      ranges[++rp].setRange(highest+1, max_jint, default_dest, NullTableIndex, cnt);

    }

  }

  assert(rp < len+2, "not too many ranges");

  if (trim_ranges) {

    merge_ranges(ranges, rp);

  }