/*

 * 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 "c1/c1_ValueStack.hpp"

#include "c1/c1_RangeCheckElimination.hpp"

#include "c1/c1_IR.hpp"

#include "c1/c1_Canonicalizer.hpp"

#include "c1/c1_ValueMap.hpp"

#include "ci/ciMethodData.hpp"

#include "runtime/deoptimization.hpp"

// Macros for the Trace and the Assertion flag

#ifdef ASSERT

#define TRACE_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination) { code; }

#define ASSERT_RANGE_CHECK_ELIMINATION(code) if (AssertRangeCheckElimination) { code; }

#define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination || AssertRangeCheckElimination) { code; }

#else

#define TRACE_RANGE_CHECK_ELIMINATION(code)

#define ASSERT_RANGE_CHECK_ELIMINATION(code)

#define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code)

#endif

// Entry point for the optimization

void RangeCheckElimination::eliminate(IR *ir) {

  bool do_elimination = ir->compilation()->has_access_indexed();

  ASSERT_RANGE_CHECK_ELIMINATION(do_elimination = true);

  if (do_elimination) {

    RangeCheckEliminator rce(ir);

  }

}

// Constructor

RangeCheckEliminator::RangeCheckEliminator(IR *ir) :

  _bounds(Instruction::number_of_instructions(), NULL),

  _access_indexed_info(Instruction::number_of_instructions(), NULL)

{

  _visitor.set_range_check_eliminator(this);

  _ir = ir;

  _number_of_instructions = Instruction::number_of_instructions();

  _optimistic = ir->compilation()->is_optimistic();

  TRACE_RANGE_CHECK_ELIMINATION(

    tty->print_cr("Range check elimination");

    ir->method()->print_name(tty);

  );

  TRACE_RANGE_CHECK_ELIMINATION(

    tty->print_cr("optimistic=%d", (int)_optimistic);

  );

#ifdef ASSERT

  // Verifies several conditions that must be true on the IR-input. Only used for debugging purposes.

  TRACE_RANGE_CHECK_ELIMINATION(

    tty->print_cr("Verification of IR . . .");

  );

  Verification verification(ir);

#endif

  // Set process block flags

  // Optimization so a blocks is only processed if it contains an access indexed instruction or if

  // one of its children in the dominator tree contains an access indexed instruction.

  set_process_block_flags(ir->start());

  // Pass over instructions in the dominator tree

  TRACE_RANGE_CHECK_ELIMINATION(

    tty->print_cr("Starting pass over dominator tree . . .")

  );

  calc_bounds(ir->start(), NULL);

  TRACE_RANGE_CHECK_ELIMINATION(

    tty->print_cr("Finished!")

  );

}

// Instruction specific work for some instructions

// Constant

void RangeCheckEliminator::Visitor::do_Constant(Constant *c) {

  IntConstant *ic = c->type()->as_IntConstant();

  if (ic != NULL) {

    int value = ic->value();

    _bound = new Bound(value, NULL, value, NULL);

  }

}

// LogicOp

void RangeCheckEliminator::Visitor::do_LogicOp(LogicOp *lo) {

  if (lo->type()->as_IntType() && lo->op() == Bytecodes::_iand && (lo->x()->as_Constant() || lo->y()->as_Constant())) {

    int constant = 0;

    Constant *c = lo->x()->as_Constant();

    if (c != NULL) {

      constant = c->type()->as_IntConstant()->value();

    } else {

      constant = lo->y()->as_Constant()->type()->as_IntConstant()->value();

    }

    if (constant >= 0) {

      _bound = new Bound(0, NULL, constant, NULL);

    }

  }

}

// Phi

void RangeCheckEliminator::Visitor::do_Phi(Phi *phi) {

  if (!phi->type()->as_IntType() && !phi->type()->as_ObjectType()) return;

  BlockBegin *block = phi->block();

  int op_count = phi->operand_count();

  bool has_upper = true;

  bool has_lower = true;

  assert(phi, "Phi must not be null");

  Bound *bound = NULL;

  // TODO: support more difficult phis

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

    Value v = phi->operand_at(i);

    if (v == phi) continue;

    // Check if instruction is connected with phi itself

    Op2 *op2 = v->as_Op2();

    if (op2 != NULL) {

      Value x = op2->x();

      Value y = op2->y();

      if ((x == phi || y == phi)) {

        Value other = x;

        if (other == phi) {

          other = y;

        }

        ArithmeticOp *ao = v->as_ArithmeticOp();

        if (ao != NULL && ao->op() == Bytecodes::_iadd) {

          assert(ao->op() == Bytecodes::_iadd, "Has to be add!");

          if (ao->type()->as_IntType()) {

            Constant *c = other->as_Constant();

            if (c != NULL) {

              assert(c->type()->as_IntConstant(), "Constant has to be of type integer");

              int value = c->type()->as_IntConstant()->value();

              if (value == 1) {

                has_upper = false;

              } else if (value > 1) {

                // Overflow not guaranteed

                has_upper = false;

                has_lower = false;

              } else if (value < 0) {

                has_lower = false;

              }

              continue;

            }

          }

        }

      }

    }

    // No connection -> new bound

    Bound *v_bound = _rce->get_bound(v);

    Bound *cur_bound;

    int cur_constant = 0;

    Value cur_value = v;

    if (v->type()->as_IntConstant()) {

      cur_constant = v->type()->as_IntConstant()->value();

      cur_value = NULL;

    }

    if (!v_bound->has_upper() || !v_bound->has_lower()) {

      cur_bound = new Bound(cur_constant, cur_value, cur_constant, cur_value);

    } else {

      cur_bound = v_bound;

    }

    if (cur_bound) {

      if (!bound) {

        bound = cur_bound->copy();

      } else {

        bound->or_op(cur_bound);

      }

    } else {

      // No bound!

      bound = NULL;

      break;

    }

  }

  if (bound) {

    if (!has_upper) {

      bound->remove_upper();

    }

    if (!has_lower) {

      bound->remove_lower();

    }

    _bound = bound;

  } else {

    _bound = new Bound();

  }

}

// ArithmeticOp

void RangeCheckEliminator::Visitor::do_ArithmeticOp(ArithmeticOp *ao) {

  Value x = ao->x();

  Value y = ao->y();

  if (ao->op() == Bytecodes::_irem) {

    Bound* x_bound = _rce->get_bound(x);

    Bound* y_bound = _rce->get_bound(y);

    if (x_bound->lower() >= 0 && x_bound->lower_instr() == NULL && y->as_ArrayLength() != NULL) {

      _bound = new Bound(0, NULL, -1, y);

    } else {

      _bound = new Bound();

    }

  } else if (!x->as_Constant() || !y->as_Constant()) {

    assert(!x->as_Constant() || !y->as_Constant(), "One of the operands must be non-constant!");

    if (((x->as_Constant() || y->as_Constant()) && (ao->op() == Bytecodes::_iadd)) || (y->as_Constant() && ao->op() == Bytecodes::_isub)) {

      assert(ao->op() == Bytecodes::_iadd || ao->op() == Bytecodes::_isub, "Operand must be iadd or isub");

      if (y->as_Constant()) {

        Value tmp = x;

        x = y;

        y = tmp;

      }

      assert(x->as_Constant()->type()->as_IntConstant(), "Constant must be int constant!");

      // Constant now in x

      int const_value = x->as_Constant()->type()->as_IntConstant()->value();

      if (ao->op() == Bytecodes::_iadd || const_value != min_jint) {

        if (ao->op() == Bytecodes::_isub) {

          const_value = -const_value;

        }

        Bound * bound = _rce->get_bound(y);

        if (bound->has_upper() && bound->has_lower()) {

          int new_lower = bound->lower() + const_value;

          jlong new_lowerl = ((jlong)bound->lower()) + const_value;

          int new_upper = bound->upper() + const_value;

          jlong new_upperl = ((jlong)bound->upper()) + const_value;

          if (((jlong)new_lower) == new_lowerl && ((jlong)new_upper == new_upperl)) {

            Bound *newBound = new Bound(new_lower, bound->lower_instr(), new_upper, bound->upper_instr());

            _bound = newBound;

          } else {

            // overflow

            _bound = new Bound();

          }

        } else {

          _bound = new Bound();

        }

      } else {

        _bound = new Bound();

      }

    } else {

      Bound *bound = _rce->get_bound(x);

      if (ao->op() == Bytecodes::_isub) {

        if (bound->lower_instr() == y) {

          _bound = new Bound(Instruction::geq, NULL, bound->lower());

        } else {

          _bound = new Bound();

        }

      } else {

        _bound = new Bound();

      }

    }

  }

}

// IfOp

void RangeCheckEliminator::Visitor::do_IfOp(IfOp *ifOp)

{

  if (ifOp->tval()->type()->as_IntConstant() && ifOp->fval()->type()->as_IntConstant()) {

    int min = ifOp->tval()->type()->as_IntConstant()->value();

    int max = ifOp->fval()->type()->as_IntConstant()->value();

    if (min > max) {

      // min ^= max ^= min ^= max;

      int tmp = min;

      min = max;

      max = tmp;

    }

    _bound = new Bound(min, NULL, max, NULL);

  }

}

// Get bound. Returns the current bound on Value v. Normally this is the topmost element on the bound stack.

RangeCheckEliminator::Bound *RangeCheckEliminator::get_bound(Value v) {

  // Wrong type or NULL -> No bound

  if (!v || (!v->type()->as_IntType() && !v->type()->as_ObjectType())) return NULL;

  if (!_bounds[v->id()]) {

    // First (default) bound is calculated

    // Create BoundStack

    _bounds[v->id()] = new BoundStack();

    _visitor.clear_bound();

    Value visit_value = v;

    visit_value->visit(&_visitor);

    Bound *bound = _visitor.bound();

    if (bound) {

      _bounds[v->id()]->push(bound);

    }

    if (_bounds[v->id()]->length() == 0) {

      assert(!(v->as_Constant() && v->type()->as_IntConstant()), "constants not handled here");

      _bounds[v->id()]->push(new Bound());

    }

  } else if (_bounds[v->id()]->length() == 0) {

    // To avoid endless loops, bound is currently in calculation -> nothing known about it

    return new Bound();

  }

  // Return bound

  return _bounds[v->id()]->top();

}

// Update bound

void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Instruction::Condition cond, Value value, int constant) {

  if (cond == Instruction::gtr) {

    cond = Instruction::geq;

    constant++;

  } else if (cond == Instruction::lss) {

    cond = Instruction::leq;

    constant--;

  }

  Bound *bound = new Bound(cond, value, constant);

  update_bound(pushed, v, bound);

}

// Checks for loop invariance. Returns true if the instruction is outside of the loop which is identified by loop_header.

bool RangeCheckEliminator::loop_invariant(BlockBegin *loop_header, Instruction *instruction) {

  assert(loop_header, "Loop header must not be null!");

  if (!instruction) return true;

  return instruction->dominator_depth() < loop_header->dominator_depth();

}

// Update bound. Pushes a new bound onto the stack. Tries to do a conjunction with the current bound.

void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Bound *bound) {

  if (v->as_Constant()) {

    // No bound update for constants

    return;

  }

  if (!_bounds[v->id()]) {

    get_bound(v);

    assert(_bounds[v->id()], "Now Stack must exist");

  }

  Bound *top = NULL;

  if (_bounds[v->id()]->length() > 0) {

    top = _bounds[v->id()]->top();

  }

  if (top) {

    bound->and_op(top);

  }

  _bounds[v->id()]->push(bound);

  pushed.append(v->id());

}

// Add instruction + idx for in block motion

void RangeCheckEliminator::add_access_indexed_info(InstructionList &indices, int idx, Value instruction, AccessIndexed *ai) {

  int id = instruction->id();

  AccessIndexedInfo *aii = _access_indexed_info[id];

  if (aii == NULL) {

    aii = new AccessIndexedInfo();

    _access_indexed_info[id] = aii;

    indices.append(instruction);

    aii->_min = idx;

    aii->_max = idx;

    aii->_list = new AccessIndexedList();

  } else if (idx >= aii->_min && idx <= aii->_max) {

    remove_range_check(ai);

    return;

  }

  aii->_min = MIN2(aii->_min, idx);

  aii->_max = MAX2(aii->_max, idx);

  aii->_list->append(ai);

}

// In block motion. Tries to reorder checks in order to reduce some of them.

// Example:

// a[i] = 0;

// a[i+2] = 0;

// a[i+1] = 0;

// In this example the check for a[i+1] would be considered as unnecessary during the first iteration.

// After this i is only checked once for i >= 0 and i+2 < a.length before the first array access. If this

// check fails, deoptimization is called.

void RangeCheckEliminator::in_block_motion(BlockBegin *block, AccessIndexedList &accessIndexed, InstructionList &arrays) {

  InstructionList indices;

  // Now iterate over all arrays

  for (int i=0; i<arrays.length(); i++) {

    int max_constant = -1;

    AccessIndexedList list_constant;

    Value array = arrays.at(i);

    // For all AccessIndexed-instructions in this block concerning the current array.

    for(int j=0; j<accessIndexed.length(); j++) {

      AccessIndexed *ai = accessIndexed.at(j);

      if (ai->array() != array || !ai->check_flag(Instruction::NeedsRangeCheckFlag)) continue;

      Value index = ai->index();

      Constant *c = index->as_Constant();

      if (c != NULL) {

        int constant_value = c->type()->as_IntConstant()->value();

        if (constant_value >= 0) {

          if (constant_value <= max_constant) {

            // No range check needed for this

            remove_range_check(ai);

          } else {

            max_constant = constant_value;

            list_constant.append(ai);

          }

        }

      } else {

        int last_integer = 0;

        Instruction *last_instruction = index;

        int base = 0;

        ArithmeticOp *ao = index->as_ArithmeticOp();

        while (ao != NULL && (ao->x()->as_Constant() || ao->y()->as_Constant()) && (ao->op() == Bytecodes::_iadd || ao->op() == Bytecodes::_isub)) {

          c = ao->y()->as_Constant();

          Instruction *other = ao->x();

          if (!c && ao->op() == Bytecodes::_iadd) {

            c = ao->x()->as_Constant();

            other = ao->y();

          }

          if (c) {

            int value = c->type()->as_IntConstant()->value();

            if (value != min_jint) {

              if (ao->op() == Bytecodes::_isub) {

                value = -value;

              }

              base += value;

              last_integer = base;

              last_instruction = other;

            }

            index = other;

          } else {

            break;

          }

          ao = index->as_ArithmeticOp();

        }

        add_access_indexed_info(indices, last_integer, last_instruction, ai);

      }

    }

    // Iterate over all different indices

    if (_optimistic) {

      for (int i = 0; i < indices.length(); i++) {

        Instruction *index_instruction = indices.at(i);

        AccessIndexedInfo *info = _access_indexed_info[index_instruction->id()];

        assert(info != NULL, "Info must not be null");

        // if idx < 0, max > 0, max + idx may fall between 0 and

        // length-1 and if min < 0, min + idx may overflow and be >=

        // 0. The predicate wouldn't trigger but some accesses could

        // be with a negative index. This test guarantees that for the

        // min and max value that are kept the predicate can't let

        // some incorrect accesses happen.

        bool range_cond = (info->_max < 0 || info->_max + min_jint <= info->_min);

        // Generate code only if more than 2 range checks can be eliminated because of that.

        // 2 because at least 2 comparisons are done

        if (info->_list->length() > 2 && range_cond) {

          AccessIndexed *first = info->_list->at(0);

          Instruction *insert_position = first->prev();

          assert(insert_position->next() == first, "prev was calculated");

          ValueStack *state = first->state_before();

          // Load min Constant

          Constant *min_constant = NULL;

          if (info->_min != 0) {

            min_constant = new Constant(new IntConstant(info->_min));

            NOT_PRODUCT(min_constant->set_printable_bci(first->printable_bci()));

            insert_position = insert_position->insert_after(min_constant);

          }

          // Load max Constant

          Constant *max_constant = NULL;

          if (info->_max != 0) {

            max_constant = new Constant(new IntConstant(info->_max));

            NOT_PRODUCT(max_constant->set_printable_bci(first->printable_bci()));

            insert_position = insert_position->insert_after(max_constant);

          }

          // Load array length

          Value length_instr = first->length();

          if (!length_instr) {

            ArrayLength *length = new ArrayLength(array, first->state_before()->copy());

            length->set_exception_state(length->state_before());

            length->set_flag(Instruction::DeoptimizeOnException, true);

            insert_position = insert_position->insert_after_same_bci(length);

            length_instr = length;

          }

          // Calculate lower bound

          Instruction *lower_compare = index_instruction;

          if (min_constant) {

            ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, min_constant, lower_compare, false, NULL);

            insert_position = insert_position->insert_after_same_bci(ao);

            lower_compare = ao;

          }

          // Calculate upper bound

          Instruction *upper_compare = index_instruction;

          if (max_constant) {

            ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, max_constant, upper_compare, false, NULL);

            insert_position = insert_position->insert_after_same_bci(ao);

            upper_compare = ao;

          }

          // Trick with unsigned compare is done

          int bci = NOT_PRODUCT(first->printable_bci()) PRODUCT_ONLY(-1);

          insert_position = predicate(upper_compare, Instruction::aeq, length_instr, state, insert_position, bci);

          insert_position = predicate_cmp_with_const(lower_compare, Instruction::leq, -1, state, insert_position);