/*

 * Copyright (c) 1999, 2011, 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) {

    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;

    }

  }

  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;

          }

        }

        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;

          }

        }

        break;

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

    }

  }

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

          }

        }

        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;

          }

        }

        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;

    }

    // 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* array = x->array()->as_NewArray();

  if (array != NULL && array->length() != NULL) {

    Constant* length = array->length()->as_Constant();

    if (length != NULL) {

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

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

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

    }

  } else {

    LoadField* lf = x->array()->as_LoadField();

    if (lf != NULL) {

      ciField* field = lf->field();

      if (field->is_constant() && field->is_static()) {

        // final static field

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

        if (c->is_array()) {

          ciArray* array = (ciArray*) c;

          set_constant(array->length());

        }

      }

    }

  }

}

void Canonicalizer::do_LoadIndexed    (LoadIndexed*     x) {}

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;

    }

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

      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;

        }

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

        }

      }

    }

  }

  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_IntConstant()->value() == 0)  set_canonical(x->x()); return;

      default       : ShouldNotReachHere();

    }

  }

}

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;

      }

    }

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

      }

    }

  }

}

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;

  }

  }

}

void Canonicalizer::do_Convert        (Convert*         x) {

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

    switch (x->op()) {

    case Bytecodes::_i2b:  set_constant((int)((x->value()->type()->as_IntConstant()->value() << 24) >> 24)); break;

    case Bytecodes::_i2s:  set_constant((int)((x->value()->type()->as_IntConstant()->value() << 16) >> 16)); break;

    case Bytecodes::_i2c:  set_constant((int)(x->value()->type()->as_IntConstant()->value() & ((1<<16)-1))); break;

    case Bytecodes::_i2l:  set_constant((jlong)(x->value()->type()->as_IntConstant()->value()));             break;

    case Bytecodes::_i2f:  set_constant((float)(x->value()->type()->as_IntConstant()->value()));             break;

    case Bytecodes::_i2d:  set_constant((double)(x->value()->type()->as_IntConstant()->value()));            break;

    case Bytecodes::_l2i:  set_constant((int)(x->value()->type()->as_LongConstant()->value()));              break;

    case Bytecodes::_l2f:  set_constant(SharedRuntime::l2f(x->value()->type()->as_LongConstant()->value())); break;

    case Bytecodes::_l2d:  set_constant(SharedRuntime::l2d(x->value()->type()->as_LongConstant()->value())); break;

    case Bytecodes::_f2d:  set_constant((double)(x->value()->type()->as_FloatConstant()->value()));          break;

    case Bytecodes::_f2i:  set_constant(SharedRuntime::f2i(x->value()->type()->as_FloatConstant()->value())); break;

    case Bytecodes::_f2l:  set_constant(SharedRuntime::f2l(x->value()->type()->as_FloatConstant()->value())); break;

    case Bytecodes::_d2f:  set_constant((float)(x->value()->type()->as_DoubleConstant()->value()));          break;

    case Bytecodes::_d2i:  set_constant(SharedRuntime::d2i(x->value()->type()->as_DoubleConstant()->value())); break;

    case Bytecodes::_d2l:  set_constant(SharedRuntime::d2l(x->value()->type()->as_DoubleConstant()->value())); break;

    default:

      ShouldNotReachHere();

    }

  }

  Value value = x->value();

  BasicType type = T_ILLEGAL;

  LoadField* lf = value->as_LoadField();

  if (lf) {

    type = lf->field_type();

  } else {

    LoadIndexed* li = value->as_LoadIndexed();

    if (li) {

      type = li->elt_type();

    } else {

      Convert* conv = value->as_Convert();

      if (conv) {

        switch (conv->op()) {

          case Bytecodes::_i2b: type = T_BYTE;  break;

          case Bytecodes::_i2s: type = T_SHORT; break;

          case Bytecodes::_i2c: type = T_CHAR;  break;

        }

      }

    }

  }

  if (type != T_ILLEGAL) {

    switch (x->op()) {

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

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

      case Bytecodes::_i2c: if (type == T_CHAR)                    set_canonical(x->value()); break;

    }

  } else {

    Op2* op2 = x->value()->as_Op2();

    if (op2 && op2->op() == Bytecodes::_iand && op2->y()->type()->is_constant()) {

      jint safebits = 0;

      jint mask = op2->y()->type()->as_IntConstant()->value();

      switch (x->op()) {

        case Bytecodes::_i2b: safebits = 0x7f;   break;

        case Bytecodes::_i2s: safebits = 0x7fff; break;

        case Bytecodes::_i2c: safebits = 0xffff; break;

      }

      // When casting a masked integer to a smaller signed type, if

      // the mask doesn't include the sign bit the cast isn't needed.

      if (safebits && (mask & ~safebits) == 0) {

        set_canonical(x->value());

      }