/*

 * 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_Optimizer.hpp"

#include "c1/c1_ValueMap.hpp"

#include "c1/c1_ValueSet.hpp"

#include "c1/c1_ValueStack.hpp"

#include "utilities/bitMap.inline.hpp"

define_array(ValueSetArray, ValueSet*);

define_stack(ValueSetList, ValueSetArray);

Optimizer::Optimizer(IR* ir) {

  assert(ir->is_valid(), "IR must be valid");

  _ir = ir;

}

class CE_Eliminator: public BlockClosure {

 private:

  IR* _hir;

  int _cee_count;                                // the number of CEs successfully eliminated

  int _ifop_count;                               // the number of IfOps successfully simplified

  int _has_substitution;

 public:

  CE_Eliminator(IR* hir) : _cee_count(0), _ifop_count(0), _hir(hir) {

    _has_substitution = false;

    _hir->iterate_preorder(this);

    if (_has_substitution) {

      // substituted some ifops/phis, so resolve the substitution

      SubstitutionResolver sr(_hir);

    }

  }

  int cee_count() const                          { return _cee_count; }

  int ifop_count() const                         { return _ifop_count; }

  void adjust_exception_edges(BlockBegin* block, BlockBegin* sux) {

    int e = sux->number_of_exception_handlers();

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

      BlockBegin* xhandler = sux->exception_handler_at(i);

      block->add_exception_handler(xhandler);

      assert(xhandler->is_predecessor(sux), "missing predecessor");

      if (sux->number_of_preds() == 0) {

        // sux is disconnected from graph so disconnect from exception handlers

        xhandler->remove_predecessor(sux);

      }

      if (!xhandler->is_predecessor(block)) {

        xhandler->add_predecessor(block);

      }

    }

  }

  virtual void block_do(BlockBegin* block);

 private:

  Value make_ifop(Value x, Instruction::Condition cond, Value y, Value tval, Value fval);

};

void CE_Eliminator::block_do(BlockBegin* block) {

  // 1) find conditional expression

  // check if block ends with an If

  If* if_ = block->end()->as_If();

  if (if_ == NULL) return;

  // check if If works on int or object types

  // (we cannot handle If's working on long, float or doubles yet,

  // since IfOp doesn't support them - these If's show up if cmp

  // operations followed by If's are eliminated)

  ValueType* if_type = if_->x()->type();

  if (!if_type->is_int() && !if_type->is_object()) return;

  BlockBegin* t_block = if_->tsux();

  BlockBegin* f_block = if_->fsux();

  Instruction* t_cur = t_block->next();

  Instruction* f_cur = f_block->next();

  // one Constant may be present between BlockBegin and BlockEnd

  Value t_const = NULL;

  Value f_const = NULL;

  if (t_cur->as_Constant() != NULL && !t_cur->can_trap()) {

    t_const = t_cur;

    t_cur = t_cur->next();

  }

  if (f_cur->as_Constant() != NULL && !f_cur->can_trap()) {

    f_const = f_cur;

    f_cur = f_cur->next();

  }

  // check if both branches end with a goto

  Goto* t_goto = t_cur->as_Goto();

  if (t_goto == NULL) return;

  Goto* f_goto = f_cur->as_Goto();

  if (f_goto == NULL) return;

  // check if both gotos merge into the same block

  BlockBegin* sux = t_goto->default_sux();

  if (sux != f_goto->default_sux()) return;

  // check if at least one word was pushed on sux_state

  ValueStack* sux_state = sux->state();

  if (sux_state->stack_size() <= if_->state()->stack_size()) return;

  // check if phi function is present at end of successor stack and that

  // only this phi was pushed on the stack

  Value sux_phi = sux_state->stack_at(if_->state()->stack_size());

  if (sux_phi == NULL || sux_phi->as_Phi() == NULL || sux_phi->as_Phi()->block() != sux) return;

  if (sux_phi->type()->size() != sux_state->stack_size() - if_->state()->stack_size()) return;

  // get the values that were pushed in the true- and false-branch

  Value t_value = t_goto->state()->stack_at(if_->state()->stack_size());

  Value f_value = f_goto->state()->stack_at(if_->state()->stack_size());

  // backend does not support floats

  assert(t_value->type()->base() == f_value->type()->base(), "incompatible types");

  if (t_value->type()->is_float_kind()) return;

  // check that successor has no other phi functions but sux_phi

  // this can happen when t_block or f_block contained additonal stores to local variables

  // that are no longer represented by explicit instructions

  for_each_phi_fun(sux, phi,

                   if (phi != sux_phi) return;

                   );

  // true and false blocks can't have phis

  for_each_phi_fun(t_block, phi, return; );

  for_each_phi_fun(f_block, phi, return; );

  // 2) substitute conditional expression

  //    with an IfOp followed by a Goto

  // cut if_ away and get node before

  Instruction* cur_end = if_->prev(block);

  // append constants of true- and false-block if necessary

  // clone constants because original block must not be destroyed

  assert((t_value != f_const && f_value != t_const) || t_const == f_const, "mismatch");

  if (t_value == t_const) {

    t_value = new Constant(t_const->type());

    NOT_PRODUCT(t_value->set_printable_bci(if_->printable_bci()));

    cur_end = cur_end->set_next(t_value);

  }

  if (f_value == f_const) {

    f_value = new Constant(f_const->type());

    NOT_PRODUCT(f_value->set_printable_bci(if_->printable_bci()));

    cur_end = cur_end->set_next(f_value);

  }

  Value result = make_ifop(if_->x(), if_->cond(), if_->y(), t_value, f_value);

  assert(result != NULL, "make_ifop must return a non-null instruction");

  if (!result->is_linked() && result->can_be_linked()) {

    NOT_PRODUCT(result->set_printable_bci(if_->printable_bci()));

    cur_end = cur_end->set_next(result);

  }

  // append Goto to successor

  ValueStack* state_before = if_->is_safepoint() ? if_->state_before() : NULL;

  Goto* goto_ = new Goto(sux, state_before, if_->is_safepoint() || t_goto->is_safepoint() || f_goto->is_safepoint());

  // prepare state for Goto

  ValueStack* goto_state = if_->state();

  while (sux_state->scope() != goto_state->scope()) {

    goto_state = goto_state->caller_state();

    assert(goto_state != NULL, "states do not match up");

  }

  goto_state = goto_state->copy(ValueStack::StateAfter, goto_state->bci());

  goto_state->push(result->type(), result);

  assert(goto_state->is_same(sux_state), "states must match now");

  goto_->set_state(goto_state);

  cur_end = cur_end->set_next(goto_, goto_state->bci());

  // Adjust control flow graph

  BlockBegin::disconnect_edge(block, t_block);

  BlockBegin::disconnect_edge(block, f_block);

  if (t_block->number_of_preds() == 0) {

    BlockBegin::disconnect_edge(t_block, sux);

  }

  adjust_exception_edges(block, t_block);

  if (f_block->number_of_preds() == 0) {

    BlockBegin::disconnect_edge(f_block, sux);

  }

  adjust_exception_edges(block, f_block);

  // update block end

  block->set_end(goto_);

  // substitute the phi if possible

  if (sux_phi->as_Phi()->operand_count() == 1) {

    assert(sux_phi->as_Phi()->operand_at(0) == result, "screwed up phi");

    sux_phi->set_subst(result);

    _has_substitution = true;

  }

  // 3) successfully eliminated a conditional expression

  _cee_count++;

  if (PrintCEE) {

    tty->print_cr("%d. CEE in B%d (B%d B%d)", cee_count(), block->block_id(), t_block->block_id(), f_block->block_id());

    tty->print_cr("%d. IfOp in B%d", ifop_count(), block->block_id());

  }

  _hir->verify();

}

Value CE_Eliminator::make_ifop(Value x, Instruction::Condition cond, Value y, Value tval, Value fval) {

  if (!OptimizeIfOps) {

    return new IfOp(x, cond, y, tval, fval);

  }

  tval = tval->subst();

  fval = fval->subst();

  if (tval == fval) {

    _ifop_count++;

    return tval;

  }

  x = x->subst();

  y = y->subst();

  Constant* y_const = y->as_Constant();

  if (y_const != NULL) {

    IfOp* x_ifop = x->as_IfOp();

    if (x_ifop != NULL) {                 // x is an ifop, y is a constant

      Constant* x_tval_const = x_ifop->tval()->subst()->as_Constant();

      Constant* x_fval_const = x_ifop->fval()->subst()->as_Constant();

      if (x_tval_const != NULL && x_fval_const != NULL) {

        Instruction::Condition x_ifop_cond = x_ifop->cond();

        Constant::CompareResult t_compare_res = x_tval_const->compare(cond, y_const);

        Constant::CompareResult f_compare_res = x_fval_const->compare(cond, y_const);

        guarantee(t_compare_res != Constant::not_comparable && f_compare_res != Constant::not_comparable, "incomparable constants in IfOp");

        Value new_tval = t_compare_res == Constant::cond_true ? tval : fval;

        Value new_fval = f_compare_res == Constant::cond_true ? tval : fval;

        _ifop_count++;

        if (new_tval == new_fval) {

          return new_tval;

        } else {

          return new IfOp(x_ifop->x(), x_ifop_cond, x_ifop->y(), new_tval, new_fval);

        }

      }

    } else {

      Constant* x_const = x->as_Constant();

      if (x_const != NULL) {         // x and y are constants

        Constant::CompareResult x_compare_res = x_const->compare(cond, y_const);

        guarantee(x_compare_res != Constant::not_comparable, "incomparable constants in IfOp");

        _ifop_count++;

        return x_compare_res == Constant::cond_true ? tval : fval;

      }

    }

  }

  return new IfOp(x, cond, y, tval, fval);

}

void Optimizer::eliminate_conditional_expressions() {

  // find conditional expressions & replace them with IfOps

  CE_Eliminator ce(ir());

}

class BlockMerger: public BlockClosure {

 private:

  IR* _hir;

  int _merge_count;              // the number of block pairs successfully merged

 public:

  BlockMerger(IR* hir)

  : _hir(hir)

  , _merge_count(0)

  {

    _hir->iterate_preorder(this);

  }

  bool try_merge(BlockBegin* block) {

    BlockEnd* end = block->end();

    if (end->as_Goto() != NULL) {

      assert(end->number_of_sux() == 1, "end must have exactly one successor");

      // Note: It would be sufficient to check for the number of successors (= 1)

      //       in order to decide if this block can be merged potentially. That

      //       would then also include switch statements w/ only a default case.

      //       However, in that case we would need to make sure the switch tag

      //       expression is executed if it can produce observable side effects.

      //       We should probably have the canonicalizer simplifying such switch

      //       statements and then we are sure we don't miss these merge opportunities

      //       here (was bug - gri 7/7/99).

      BlockBegin* sux = end->default_sux();

      if (sux->number_of_preds() == 1 && !sux->is_entry_block() && !end->is_safepoint()) {

        // merge the two blocks

#ifdef ASSERT

        // verify that state at the end of block and at the beginning of sux are equal

        // no phi functions must be present at beginning of sux

        ValueStack* sux_state = sux->state();

        ValueStack* end_state = end->state();

        assert(end_state->scope() == sux_state->scope(), "scopes must match");

        assert(end_state->stack_size() == sux_state->stack_size(), "stack not equal");

        assert(end_state->locals_size() == sux_state->locals_size(), "locals not equal");

        int index;

        Value sux_value;

        for_each_stack_value(sux_state, index, sux_value) {

          assert(sux_value == end_state->stack_at(index), "stack not equal");

        }

        for_each_local_value(sux_state, index, sux_value) {

          assert(sux_value == end_state->local_at(index), "locals not equal");

        }

        assert(sux_state->caller_state() == end_state->caller_state(), "caller not equal");

#endif

        // find instruction before end & append first instruction of sux block

        Instruction* prev = end->prev(block);

        Instruction* next = sux->next();

        assert(prev->as_BlockEnd() == NULL, "must not be a BlockEnd");

        prev->set_next(next);

        sux->disconnect_from_graph();

        block->set_end(sux->end());

        // add exception handlers of deleted block, if any

        for (int k = 0; k < sux->number_of_exception_handlers(); k++) {

          BlockBegin* xhandler = sux->exception_handler_at(k);

          block->add_exception_handler(xhandler);

          // also substitute predecessor of exception handler

          assert(xhandler->is_predecessor(sux), "missing predecessor");

          xhandler->remove_predecessor(sux);

          if (!xhandler->is_predecessor(block)) {

            xhandler->add_predecessor(block);

          }

        }

        // debugging output

        _merge_count++;

        if (PrintBlockElimination) {

          tty->print_cr("%d. merged B%d & B%d (stack size = %d)",

                        _merge_count, block->block_id(), sux->block_id(), sux->state()->stack_size());

        }

        _hir->verify();

        If* if_ = block->end()->as_If();

        if (if_) {

          IfOp* ifop    = if_->x()->as_IfOp();

          Constant* con = if_->y()->as_Constant();

          bool swapped = false;

          if (!con || !ifop) {

            ifop = if_->y()->as_IfOp();

            con  = if_->x()->as_Constant();

            swapped = true;

          }

          if (con && ifop) {

            Constant* tval = ifop->tval()->as_Constant();

            Constant* fval = ifop->fval()->as_Constant();

            if (tval && fval) {

              // Find the instruction before if_, starting with ifop.

              // When if_ and ifop are not in the same block, prev

              // becomes NULL In such (rare) cases it is not

              // profitable to perform the optimization.

              Value prev = ifop;

              while (prev != NULL && prev->next() != if_) {

                prev = prev->next();

              }

              if (prev != NULL) {

                Instruction::Condition cond = if_->cond();

                BlockBegin* tsux = if_->tsux();

                BlockBegin* fsux = if_->fsux();

                if (swapped) {

                  cond = Instruction::mirror(cond);

                }

                BlockBegin* tblock = tval->compare(cond, con, tsux, fsux);

                BlockBegin* fblock = fval->compare(cond, con, tsux, fsux);

                if (tblock != fblock && !if_->is_safepoint()) {

                  If* newif = new If(ifop->x(), ifop->cond(), false, ifop->y(),

                                     tblock, fblock, if_->state_before(), if_->is_safepoint());

                  newif->set_state(if_->state()->copy());

                  assert(prev->next() == if_, "must be guaranteed by above search");

                  NOT_PRODUCT(newif->set_printable_bci(if_->printable_bci()));

                  prev->set_next(newif);

                  block->set_end(newif);

                  _merge_count++;

                  if (PrintBlockElimination) {

                    tty->print_cr("%d. replaced If and IfOp at end of B%d with single If", _merge_count, block->block_id());

                  }

                  _hir->verify();

                }

              }

            }

          }

        }

        return true;

      }

    }

    return false;

  }

  virtual void block_do(BlockBegin* block) {

    _hir->verify();

    // repeat since the same block may merge again

    while (try_merge(block)) {

      _hir->verify();

    }

  }

};

void Optimizer::eliminate_blocks() {

  // merge blocks if possible

  BlockMerger bm(ir());

}

class NullCheckEliminator;

class NullCheckVisitor: public InstructionVisitor {

private:

  NullCheckEliminator* _nce;

  NullCheckEliminator* nce() { return _nce; }

public:

  NullCheckVisitor() {}

  void set_eliminator(NullCheckEliminator* nce) { _nce = nce; }

  void do_Phi            (Phi*             x);

  void do_Local          (Local*           x);

  void do_Constant       (Constant*        x);

  void do_LoadField      (LoadField*       x);

  void do_StoreField     (StoreField*      x);

  void do_ArrayLength    (ArrayLength*     x);

  void do_LoadIndexed    (LoadIndexed*     x);

  void do_StoreIndexed   (StoreIndexed*    x);

  void do_NegateOp       (NegateOp*        x);

  void do_ArithmeticOp   (ArithmeticOp*    x);

  void do_ShiftOp        (ShiftOp*         x);

  void do_LogicOp        (LogicOp*         x);

  void do_CompareOp      (CompareOp*       x);

  void do_IfOp           (IfOp*            x);

  void do_Convert        (Convert*         x);

  void do_NullCheck      (NullCheck*       x);

  void do_Invoke         (Invoke*          x);

  void do_NewInstance    (NewInstance*     x);

  void do_NewTypeArray   (NewTypeArray*    x);

  void do_NewObjectArray (NewObjectArray*  x);

  void do_NewMultiArray  (NewMultiArray*   x);

  void do_CheckCast      (CheckCast*       x);

  void do_InstanceOf     (InstanceOf*      x);

  void do_MonitorEnter   (MonitorEnter*    x);

  void do_MonitorExit    (MonitorExit*     x);

  void do_Intrinsic      (Intrinsic*       x);

  void do_BlockBegin     (BlockBegin*      x);

  void do_Goto           (Goto*            x);

  void do_If             (If*              x);

  void do_IfInstanceOf   (IfInstanceOf*    x);

  void do_TableSwitch    (TableSwitch*     x);

  void do_LookupSwitch   (LookupSwitch*    x);

  void do_Return         (Return*          x);

  void do_Throw          (Throw*           x);

  void do_Base           (Base*            x);

  void do_OsrEntry       (OsrEntry*        x);

  void do_ExceptionObject(ExceptionObject* x);

  void do_RoundFP        (RoundFP*         x);

  void do_UnsafeGetRaw   (UnsafeGetRaw*    x);

  void do_UnsafePutRaw   (UnsafePutRaw*    x);

  void do_UnsafeGetObject(UnsafeGetObject* x);

  void do_UnsafePutObject(UnsafePutObject* x);

  void do_UnsafePrefetchRead (UnsafePrefetchRead*  x);

  void do_UnsafePrefetchWrite(UnsafePrefetchWrite* x);

  void do_ProfileCall    (ProfileCall*     x);

  void do_ProfileInvoke  (ProfileInvoke*   x);

  void do_RuntimeCall    (RuntimeCall*     x);

};

// Because of a static contained within (for the purpose of iteration

// over instructions), it is only valid to have one of these active at

// a time

class NullCheckEliminator: public ValueVisitor {

 private:

  Optimizer*        _opt;

  ValueSet*         _visitable_instructions;        // Visit each instruction only once per basic block