/*

 * Copyright 1998-2007 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

#include "incls/_precompiled.incl"

#include "incls/_parse2.cpp.incl"

extern int explicit_null_checks_inserted,

           explicit_null_checks_elided;

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

void Parse::array_load(BasicType elem_type) {

  const Type* elem = Type::TOP;

  Node* adr = array_addressing(elem_type, 0, &elem);

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

  _sp -= 2;                   // Pop array and index

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

  Node* ld = make_load(control(), adr, elem, elem_type, adr_type);

  push(ld);

}

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

void Parse::array_store(BasicType elem_type) {

  Node* adr = array_addressing(elem_type, 1);

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

  Node* val = pop();

  _sp -= 2;                   // Pop array and index

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

  store_to_memory(control(), adr, val, elem_type, adr_type);

}

//------------------------------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 = do_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 TypeInstPtr* toop = elemtype->isa_instptr();

    if (toop) {

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

      }

    }

  }

  // 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'");

  }

  if (!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) {

    // 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 (C, 3) CmpUNode(idx, len) );

    BoolTest::mask btest = BoolTest::lt;

    Node* tst = _gvn.transform( new (C, 2) BoolNode(chk, btest) );

    // Branch to failure if out of bounds

    { BuildCutout unless(this, tst, PROB_MAX);

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

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

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

  return ptr;

}

// returns IfNode

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

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

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

  IfNode *iff = create_and_map_if( control(), tst, ((mask == BoolTest::eq) ? PROB_STATIC_INFREQUENT : PROB_FAIR), COUNT_UNKNOWN );

  return iff;

}

// return Region node

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

  Node *region  = new (C, 3) 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;

}

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

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

  // True branch, use existing map info

  { PreserveJVMState pjvms(this);

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

    set_control( iftrue );

    profile_switch_case(prof_table_index);

    merge_new_path(dest_bci_if_true);

  }

  // False branch

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

  set_control( iffalse );

}

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

  // True branch, use existing map info

  { PreserveJVMState pjvms(this);

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

    set_control( iffalse );

    profile_switch_case(prof_table_index);

    merge_new_path(dest_bci_if_true);

  }

  // False branch

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

  set_control( iftrue );

}

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

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

  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

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

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

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

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

  }

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

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

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

      _hi = hi;

      return true;

    }

    return false;

  }

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

    setRange(value, value, dest, table_index);

  }

  bool adjoin(jint value, int dest, int table_index) {

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

  }

  void print(ciEnv* env) {

    if (is_singleton())

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

    else if (lo() == min_jint)

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

    else if (hi() == max_jint)

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

    else

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

  }

};

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

  }

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

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

  }

  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;

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

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

    }

  }

  jint highest = lo_index+(len-1);

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

  if (highest != max_jint

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

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

  }

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

  // Safepoint in case if backward branch observed

  if( makes_backward_branch && UseLoopSafepoints )

    add_safepoint();

  jump_switch_ranges(lookup, &ranges[0], &ranges[rp]);

}

//------------------------------do_lookupswitch--------------------------------

void Parse::do_lookupswitch() {

  Node *lookup = pop();         // lookup value

  // Get information about lookupswitch

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

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

  if (len < 1) {    // If this is a backward branch, add safepoint

    maybe_add_safepoint(default_dest);

    merge(default_dest);

    return;

  }

  // generate decision tree, using trichotomy when possible

  jint* table = NEW_RESOURCE_ARRAY(jint, len*2);

  {

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

      table[j+j+0] = iter().get_int_table(2+j+j);

      table[j+j+1] = iter().get_dest_table(2+j+j+1);

    }

    qsort( table, len, 2*sizeof(table[0]), jint_cmp );

  }

  int rnum = len*2+1;

  bool makes_backward_branch = false;

  SwitchRange* ranges = NEW_RESOURCE_ARRAY(SwitchRange, rnum);

  int rp = -1;

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

    jint match_int   = table[j+j+0];

    int  dest        = table[j+j+1];

    int  next_lo     = rp < 0 ? min_jint : ranges[rp].hi()+1;

    int  table_index = method_data_update() ? j : NullTableIndex;

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

    if( match_int != next_lo ) {

      ranges[++rp].setRange(next_lo, match_int-1, default_dest, NullTableIndex);

    }

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

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

    }

  }

  jint highest = table[2*(len-1)];

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

  if( highest != max_jint

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

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

  }

  assert(rp < rnum, "not too many ranges");

  // Safepoint in case backward branch observed

  if( makes_backward_branch && UseLoopSafepoints )

    add_safepoint();

  jump_switch_ranges(lookup, &ranges[0], &ranges[rp]);

}

//----------------------------create_jump_tables-------------------------------

bool Parse::create_jump_tables(Node* key_val, SwitchRange* lo, SwitchRange* hi) {

  // Are jumptables enabled

  if (!UseJumpTables)  return false;

  // Are jumptables supported

  if (!Matcher::has_match_rule(Op_Jump))  return false;

  // Don't make jump table if profiling

  if (method_data_update())  return false;

  // Decide if a guard is needed to lop off big ranges at either (or

  // both) end(s) of the input set. We'll call this the default target

  // even though we can't be sure that it is the true "default".

  bool needs_guard = false;

  int default_dest;

  int64 total_outlier_size = 0;

  int64 hi_size = ((int64)hi->hi()) - ((int64)hi->lo()) + 1;

  int64 lo_size = ((int64)lo->hi()) - ((int64)lo->lo()) + 1;

  if (lo->dest() == hi->dest()) {

    total_outlier_size = hi_size + lo_size;

    default_dest = lo->dest();

  } else if (lo_size > hi_size) {

    total_outlier_size = lo_size;

    default_dest = lo->dest();

  } else {

    total_outlier_size = hi_size;

    default_dest = hi->dest();

  }

  // If a guard test will eliminate very sparse end ranges, then

  // it is worth the cost of an extra jump.

  if (total_outlier_size > (MaxJumpTableSparseness * 4)) {

    needs_guard = true;

    if (default_dest == lo->dest()) lo++;

    if (default_dest == hi->dest()) hi--;

  }

  // Find the total number of cases and ranges

  int64 num_cases = ((int64)hi->hi()) - ((int64)lo->lo()) + 1;

  int num_range = hi - lo + 1;

  // Don't create table if: too large, too small, or too sparse.

  if (num_cases < MinJumpTableSize || num_cases > MaxJumpTableSize)

    return false;

  if (num_cases > (MaxJumpTableSparseness * num_range))

    return false;

  // Normalize table lookups to zero

  int lowval = lo->lo();

  key_val = _gvn.transform( new (C, 3) SubINode(key_val, _gvn.intcon(lowval)) );

  // Generate a guard to protect against input keyvals that aren't

  // in the switch domain.

  if (needs_guard) {

    Node*   size = _gvn.intcon(num_cases);

    Node*   cmp = _gvn.transform( new (C, 3) CmpUNode(key_val, size) );

    Node*   tst = _gvn.transform( new (C, 2) BoolNode(cmp, BoolTest::ge) );

    IfNode* iff = create_and_map_if( control(), tst, PROB_FAIR, COUNT_UNKNOWN);

    jump_if_true_fork(iff, default_dest, NullTableIndex);

  }

  // Create an ideal node JumpTable that has projections

  // of all possible ranges for a switch statement

  // The key_val input must be converted to a pointer offset and scaled.

  // Compare Parse::array_addressing above.

#ifdef _LP64

  // Clean the 32-bit int into a real 64-bit offset.

  // Otherwise, the jint value 0 might turn into an offset of 0x0800000000.

  const TypeLong* lkeytype = TypeLong::make(CONST64(0), num_cases-1, Type::WidenMin);

  key_val       = _gvn.transform( new (C, 2) ConvI2LNode(key_val, lkeytype) );

#endif

  // Shift the value by wordsize so we have an index into the table, rather

  // than a switch value

  Node *shiftWord = _gvn.MakeConX(wordSize);

  key_val = _gvn.transform( new (C, 3) MulXNode( key_val, shiftWord));

  // Create the JumpNode

  Node* jtn = _gvn.transform( new (C, 2) JumpNode(control(), key_val, num_cases) );

  // These are the switch destinations hanging off the jumpnode

  int i = 0;

  for (SwitchRange* r = lo; r <= hi; r++) {

    for (int j = r->lo(); j <= r->hi(); j++, i++) {

      Node* input = _gvn.transform(new (C, 1) JumpProjNode(jtn, i, r->dest(), j - lowval));

      {

        PreserveJVMState pjvms(this);

        set_control(input);

        jump_if_always_fork(r->dest(), r->table_index());

      }

    }

  }

  assert(i == num_cases, "miscount of cases");

  stop_and_kill_map();  // no more uses for this JVMS

  return true;

}

//----------------------------jump_switch_ranges-------------------------------

void Parse::jump_switch_ranges(Node* key_val, SwitchRange *lo, SwitchRange *hi, int switch_depth) {

  Block* switch_block = block();

  if (switch_depth == 0) {

    // Do special processing for the top-level call.

    assert(lo->lo() == min_jint, "initial range must exhaust Type::INT");

    assert(hi->hi() == max_jint, "initial range must exhaust Type::INT");

    // Decrement pred-numbers for the unique set of nodes.

#ifdef ASSERT

    // Ensure that the block's successors are a (duplicate-free) set.

    int successors_counted = 0;  // block occurrences in [hi..lo]

    int unique_successors = switch_block->num_successors();

    for (int i = 0; i < unique_successors; i++) {

      Block* target = switch_block->successor_at(i);

      // Check that the set of successors is the same in both places.

      int successors_found = 0;

      for (SwitchRange* p = lo; p <= hi; p++) {

        if (p->dest() == target->start())  successors_found++;

      }

      assert(successors_found > 0, "successor must be known");

      successors_counted += successors_found;

    }

    assert(successors_counted == (hi-lo)+1, "no unexpected successors");

#endif

    // Maybe prune the inputs, based on the type of key_val.

    jint min_val = min_jint;

    jint max_val = max_jint;

    const TypeInt* ti = key_val->bottom_type()->isa_int();

    if (ti != NULL) {

      min_val = ti->_lo;

      max_val = ti->_hi;

      assert(min_val <= max_val, "invalid int type");

    }

    while (lo->hi() < min_val)  lo++;

    if (lo->lo() < min_val)  lo->setRange(min_val, lo->hi(), lo->dest(), lo->table_index());

    while (hi->lo() > max_val)  hi--;

    if (hi->hi() > max_val)  hi->setRange(hi->lo(), max_val, hi->dest(), hi->table_index());

  }

#ifndef PRODUCT

  if (switch_depth == 0) {

    _max_switch_depth = 0;

    _est_switch_depth = log2_intptr((hi-lo+1)-1)+1;

  }

#endif

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

  if (lo == hi) {

    jump_if_always_fork(lo->dest(), lo->table_index());

  } else {

    assert(lo->hi() == (lo+1)->lo()-1, "contiguous ranges");

    assert(hi->lo() == (hi-1)->hi()+1, "contiguous ranges");

    if (create_jump_tables(key_val, lo, hi)) return;

    int nr = hi - lo + 1;

    SwitchRange* mid = lo + nr/2;

    // if there is an easy choice, pivot at a singleton:

    if (nr > 3 && !mid->is_singleton() && (mid-1)->is_singleton())  mid--;

    assert(lo < mid && mid <= hi, "good pivot choice");

    assert(nr != 2 || mid == hi,   "should pick higher of 2");

    assert(nr != 3 || mid == hi-1, "should pick middle of 3");

    Node *test_val = _gvn.intcon(mid->lo());