/*

 * Copyright (c) 1999, 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 "c1/c1_Canonicalizer.hpp"

#include "c1/c1_InstructionPrinter.hpp"

#include "c1/c1_ValueStack.hpp"

#include "ci/ciArray.hpp"

#include "runtime/sharedRuntime.hpp"

class PrintValueVisitor: public ValueVisitor {

  void visit(Value* vp) {

    (*vp)->print_line();

  }

};

void Canonicalizer::set_canonical(Value x) {

  assert(x != NULL, "value must exist");

  // Note: we can not currently substitute root nodes which show up in

  // the instruction stream (because the instruction list is embedded

  // in the instructions).

  if (canonical() != x) {

#ifndef PRODUCT

    if (!x->has_printable_bci()) {

      x->set_printable_bci(bci());

    }

#endif

    if (PrintCanonicalization) {

      PrintValueVisitor do_print_value;

      canonical()->input_values_do(&do_print_value);

      canonical()->print_line();

      tty->print_cr("canonicalized to:");

      x->input_values_do(&do_print_value);

      x->print_line();

      tty->cr();

    }

    assert(_canonical->type()->tag() == x->type()->tag(), "types must match");

    _canonical = x;

  }

}

void Canonicalizer::move_const_to_right(Op2* x) {

  if (x->x()->type()->is_constant() && x->is_commutative()) x->swap_operands();

}

void Canonicalizer::do_Op2(Op2* x) {

  if (x->x() == x->y()) {

    switch (x->op()) {

    case Bytecodes::_isub: set_constant(0); return;

    case Bytecodes::_lsub: set_constant(jlong_cast(0)); return;

    case Bytecodes::_iand: // fall through

    case Bytecodes::_land: // fall through

    case Bytecodes::_ior : // fall through

    case Bytecodes::_lor : set_canonical(x->x()); return;

    case Bytecodes::_ixor: set_constant(0); return;

    case Bytecodes::_lxor: set_constant(jlong_cast(0)); return;

    default              : break;

    }

  }

  if (x->x()->type()->is_constant() && x->y()->type()->is_constant()) {

    // do constant folding for selected operations

    switch (x->type()->tag()) {

      case intTag:

        { jint a = x->x()->type()->as_IntConstant()->value();

          jint b = x->y()->type()->as_IntConstant()->value();

          switch (x->op()) {

            case Bytecodes::_iadd: set_constant(a + b); return;

            case Bytecodes::_isub: set_constant(a - b); return;

            case Bytecodes::_imul: set_constant(a * b); return;

            case Bytecodes::_idiv:

              if (b != 0) {

                if (a == min_jint && b == -1) {

                  set_constant(min_jint);

                } else {

                  set_constant(a / b);

                }

                return;

              }

              break;

            case Bytecodes::_irem:

              if (b != 0) {

                if (a == min_jint && b == -1) {

                  set_constant(0);

                } else {

                  set_constant(a % b);

                }

                return;

              }

              break;

            case Bytecodes::_iand: set_constant(a & b); return;

            case Bytecodes::_ior : set_constant(a | b); return;

            case Bytecodes::_ixor: set_constant(a ^ b); return;

            default              : break;

          }

        }

        break;

      case longTag:

        { jlong a = x->x()->type()->as_LongConstant()->value();

          jlong b = x->y()->type()->as_LongConstant()->value();

          switch (x->op()) {

            case Bytecodes::_ladd: set_constant(a + b); return;

            case Bytecodes::_lsub: set_constant(a - b); return;

            case Bytecodes::_lmul: set_constant(a * b); return;

            case Bytecodes::_ldiv:

              if (b != 0) {

                set_constant(SharedRuntime::ldiv(b, a));

                return;

              }

              break;

            case Bytecodes::_lrem:

              if (b != 0) {

                set_constant(SharedRuntime::lrem(b, a));

                return;

              }

              break;

            case Bytecodes::_land: set_constant(a & b); return;

            case Bytecodes::_lor : set_constant(a | b); return;

            case Bytecodes::_lxor: set_constant(a ^ b); return;

            default              : break;

          }

        }

        break;

      default:

        // other cases not implemented (must be extremely careful with floats & doubles!)

        break;

    }

  }

  // make sure constant is on the right side, if any

  move_const_to_right(x);

  if (x->y()->type()->is_constant()) {

    // do constant folding for selected operations

    switch (x->type()->tag()) {

      case intTag:

        if (x->y()->type()->as_IntConstant()->value() == 0) {

          switch (x->op()) {

            case Bytecodes::_iadd: set_canonical(x->x()); return;

            case Bytecodes::_isub: set_canonical(x->x()); return;

            case Bytecodes::_imul: set_constant(0); return;

              // Note: for div and rem, make sure that C semantics

              //       corresponds to Java semantics!

            case Bytecodes::_iand: set_constant(0); return;

            case Bytecodes::_ior : set_canonical(x->x()); return;

            default              : break;

          }

        }

        break;

      case longTag:

        if (x->y()->type()->as_LongConstant()->value() == (jlong)0) {

          switch (x->op()) {

            case Bytecodes::_ladd: set_canonical(x->x()); return;

            case Bytecodes::_lsub: set_canonical(x->x()); return;

            case Bytecodes::_lmul: set_constant((jlong)0); return;

              // Note: for div and rem, make sure that C semantics

              //       corresponds to Java semantics!

            case Bytecodes::_land: set_constant((jlong)0); return;

            case Bytecodes::_lor : set_canonical(x->x()); return;

            default              : break;

          }

        }

        break;

      default:

        break;

    }

  }

}

void Canonicalizer::do_Phi            (Phi*             x) {}

void Canonicalizer::do_Constant       (Constant*        x) {}

void Canonicalizer::do_Local          (Local*           x) {}

void Canonicalizer::do_LoadField      (LoadField*       x) {}

// checks if v is in the block that is currently processed by

// GraphBuilder. This is the only block that has not BlockEnd yet.

static bool in_current_block(Value v) {

  int max_distance = 4;

  while (max_distance > 0 && v != NULL && v->as_BlockEnd() == NULL) {

    v = v->next();

    max_distance--;

  }

  return v == NULL;

}

void Canonicalizer::do_StoreField     (StoreField*      x) {

  // If a value is going to be stored into a field or array some of

  // the conversions emitted by javac are unneeded because the fields

  // are packed to their natural size.

  Convert* conv = x->value()->as_Convert();

  if (conv) {

    Value value = NULL;

    BasicType type = x->field()->type()->basic_type();

    switch (conv->op()) {

    case Bytecodes::_i2b: if (type == T_BYTE)  value = conv->value(); break;

    case Bytecodes::_i2s: if (type == T_SHORT || type == T_BYTE) value = conv->value(); break;

    case Bytecodes::_i2c: if (type == T_CHAR  || type == T_BYTE)  value = conv->value(); break;

    default             : break;

    }

    // limit this optimization to current block

    if (value != NULL && in_current_block(conv)) {

      set_canonical(new StoreField(x->obj(), x->offset(), x->field(), value, x->is_static(),

                                   x->state_before(), x->needs_patching()));

      return;

    }

  }

}

void Canonicalizer::do_ArrayLength    (ArrayLength*     x) {

  NewArray*  na;

  Constant*  ct;

  LoadField* lf;

  if ((na = x->array()->as_NewArray()) != NULL) {

    // New arrays might have the known length.

    // Do not use the Constant itself, but create a new Constant

    // with same value Otherwise a Constant is live over multiple

    // blocks without being registered in a state array.

    Constant* length;

    if (na->length() != NULL &&

        (length = na->length()->as_Constant()) != NULL) {

      assert(length->type()->as_IntConstant() != NULL, "array length must be integer");

      set_constant(length->type()->as_IntConstant()->value());

    }

  } else if ((ct = x->array()->as_Constant()) != NULL) {

    // Constant arrays have constant lengths.

    ArrayConstant* cnst = ct->type()->as_ArrayConstant();

    if (cnst != NULL) {

      set_constant(cnst->value()->length());

    }

  } else if ((lf = x->array()->as_LoadField()) != NULL) {

    ciField* field = lf->field();

    if (field->is_static_constant()) {

      // Constant field loads are usually folded during parsing.

      // But it doesn't happen with PatchALot, ScavengeRootsInCode < 2, or when

      // holder class is being initialized during parsing (for static fields).

      ciObject* c = field->constant_value().as_object();

      if (!c->is_null_object()) {

        set_constant(c->as_array()->length());

      }

    }

  }

}

void Canonicalizer::do_LoadIndexed    (LoadIndexed*     x) {

  StableArrayConstant* array = x->array()->type()->as_StableArrayConstant();

  IntConstant* index = x->index()->type()->as_IntConstant();

  assert(array == NULL || FoldStableValues, "not enabled");

  // Constant fold loads from stable arrays.

  if (!x->mismatched() && array != NULL && index != NULL) {

    jint idx = index->value();

    if (idx < 0 || idx >= array->value()->length()) {

      // Leave the load as is. The range check will handle it.

      return;

    }

    ciConstant field_val = array->value()->element_value(idx);

    if (!field_val.is_null_or_zero()) {

      jint dimension = array->dimension();

      assert(dimension <= array->value()->array_type()->dimension(), "inconsistent info");

      ValueType* value = NULL;

      if (dimension > 1) {

        // Preserve information about the dimension for the element.

        assert(field_val.as_object()->is_array(), "not an array");

        value = new StableArrayConstant(field_val.as_object()->as_array(), dimension - 1);

      } else {

        assert(dimension == 1, "sanity");

        value = as_ValueType(field_val);

      }

      set_canonical(new Constant(value));

    }

  }

}

void Canonicalizer::do_StoreIndexed   (StoreIndexed*    x) {

  // If a value is going to be stored into a field or array some of

  // the conversions emitted by javac are unneeded because the fields

  // are packed to their natural size.

  Convert* conv = x->value()->as_Convert();

  if (conv) {

    Value value = NULL;

    BasicType type = x->elt_type();

    switch (conv->op()) {

    case Bytecodes::_i2b: if (type == T_BYTE)  value = conv->value(); break;

    case Bytecodes::_i2s: if (type == T_SHORT || type == T_BYTE) value = conv->value(); break;

    case Bytecodes::_i2c: if (type == T_CHAR  || type == T_BYTE) value = conv->value(); break;

    default             : break;

    }

    // limit this optimization to current block

    if (value != NULL && in_current_block(conv)) {

      set_canonical(new StoreIndexed(x->array(), x->index(), x->length(),

                                     x->elt_type(), value, x->state_before(),

                                     x->check_boolean()));

      return;

    }

  }

}

void Canonicalizer::do_NegateOp(NegateOp* x) {

  ValueType* t = x->x()->type();

  if (t->is_constant()) {

    switch (t->tag()) {

      case intTag   : set_constant(-t->as_IntConstant   ()->value()); return;

      case longTag  : set_constant(-t->as_LongConstant  ()->value()); return;

      case floatTag : set_constant(-t->as_FloatConstant ()->value()); return;

      case doubleTag: set_constant(-t->as_DoubleConstant()->value()); return;

      default       : ShouldNotReachHere();

    }

  }

}

void Canonicalizer::do_ArithmeticOp   (ArithmeticOp*    x) { do_Op2(x); }

void Canonicalizer::do_ShiftOp        (ShiftOp*         x) {

  ValueType* t = x->x()->type();

  ValueType* t2 = x->y()->type();

  if (t->is_constant()) {

    switch (t->tag()) {

    case intTag   : if (t->as_IntConstant()->value() == 0)         { set_constant(0); return; } break;

    case longTag  : if (t->as_LongConstant()->value() == (jlong)0) { set_constant(jlong_cast(0)); return; } break;

    default       : ShouldNotReachHere();

    }

    if (t2->is_constant()) {

      if (t->tag() == intTag) {

        int value = t->as_IntConstant()->value();

        int shift = t2->as_IntConstant()->value() & 31;

        jint mask = ~(~0 << (32 - shift));

        if (shift == 0) mask = ~0;

        switch (x->op()) {

          case Bytecodes::_ishl:  set_constant(value << shift); return;

          case Bytecodes::_ishr:  set_constant(value >> shift); return;

          case Bytecodes::_iushr: set_constant((value >> shift) & mask); return;

          default:                break;

        }

      } else if (t->tag() == longTag) {

        jlong value = t->as_LongConstant()->value();

        int shift = t2->as_IntConstant()->value() & 63;

        jlong mask = ~(~jlong_cast(0) << (64 - shift));

        if (shift == 0) mask = ~jlong_cast(0);

        switch (x->op()) {

          case Bytecodes::_lshl:  set_constant(value << shift); return;

          case Bytecodes::_lshr:  set_constant(value >> shift); return;

          case Bytecodes::_lushr: set_constant((value >> shift) & mask); return;

          default:                break;

        }

      }

    }

  }

  if (t2->is_constant()) {

    switch (t2->tag()) {

      case intTag   : if (t2->as_IntConstant()->value() == 0)  set_canonical(x->x()); return;

      case longTag  : if (t2->as_LongConstant()->value() == (jlong)0)  set_canonical(x->x()); return;

      default       : ShouldNotReachHere(); return;

    }

  }

}

void Canonicalizer::do_LogicOp        (LogicOp*         x) { do_Op2(x); }

void Canonicalizer::do_CompareOp      (CompareOp*       x) {

  if (x->x() == x->y()) {

    switch (x->x()->type()->tag()) {

      case longTag: set_constant(0); break;

      case floatTag: {

        FloatConstant* fc = x->x()->type()->as_FloatConstant();

        if (fc) {

          if (g_isnan(fc->value())) {

            set_constant(x->op() == Bytecodes::_fcmpl ? -1 : 1);

          } else {

            set_constant(0);

          }

        }

        break;

      }

      case doubleTag: {

        DoubleConstant* dc = x->x()->type()->as_DoubleConstant();

        if (dc) {

          if (g_isnan(dc->value())) {

            set_constant(x->op() == Bytecodes::_dcmpl ? -1 : 1);

          } else {

            set_constant(0);

          }

        }

        break;

      }

      default:

        break;

    }

  } else if (x->x()->type()->is_constant() && x->y()->type()->is_constant()) {

    switch (x->x()->type()->tag()) {

      case longTag: {

        jlong vx = x->x()->type()->as_LongConstant()->value();

        jlong vy = x->y()->type()->as_LongConstant()->value();

        if (vx == vy)

          set_constant(0);

        else if (vx < vy)

          set_constant(-1);

        else

          set_constant(1);

        break;

      }

      case floatTag: {

        float vx = x->x()->type()->as_FloatConstant()->value();

        float vy = x->y()->type()->as_FloatConstant()->value();

        if (g_isnan(vx) || g_isnan(vy))

          set_constant(x->op() == Bytecodes::_fcmpl ? -1 : 1);

        else if (vx == vy)

          set_constant(0);

        else if (vx < vy)

          set_constant(-1);

        else

          set_constant(1);

        break;

      }

      case doubleTag: {

        double vx = x->x()->type()->as_DoubleConstant()->value();

        double vy = x->y()->type()->as_DoubleConstant()->value();

        if (g_isnan(vx) || g_isnan(vy))

          set_constant(x->op() == Bytecodes::_dcmpl ? -1 : 1);

        else if (vx == vy)

          set_constant(0);

        else if (vx < vy)

          set_constant(-1);

        else

          set_constant(1);

        break;

      }

      default:

        break;

    }

  }

}

void Canonicalizer::do_IfInstanceOf(IfInstanceOf*    x) {}

void Canonicalizer::do_IfOp(IfOp* x) {

  // Caution: do not use do_Op2(x) here for now since

  //          we map the condition to the op for now!

  move_const_to_right(x);

}

void Canonicalizer::do_Intrinsic      (Intrinsic*       x) {

  switch (x->id()) {

  case vmIntrinsics::_floatToRawIntBits   : {

    FloatConstant* c = x->argument_at(0)->type()->as_FloatConstant();

    if (c != NULL) {

      JavaValue v;

      v.set_jfloat(c->value());

      set_constant(v.get_jint());

    }

    break;

  }

  case vmIntrinsics::_intBitsToFloat      : {

    IntConstant* c = x->argument_at(0)->type()->as_IntConstant();

    if (c != NULL) {

      JavaValue v;

      v.set_jint(c->value());

      set_constant(v.get_jfloat());

    }

    break;

  }

  case vmIntrinsics::_doubleToRawLongBits : {

    DoubleConstant* c = x->argument_at(0)->type()->as_DoubleConstant();

    if (c != NULL) {

      JavaValue v;

      v.set_jdouble(c->value());

      set_constant(v.get_jlong());

    }

    break;

  }

  case vmIntrinsics::_longBitsToDouble    : {

    LongConstant* c = x->argument_at(0)->type()->as_LongConstant();

    if (c != NULL) {

      JavaValue v;

      v.set_jlong(c->value());

      set_constant(v.get_jdouble());

    }

    break;

  }

  case vmIntrinsics::_isInstance          : {