/*

 * Copyright (c) 1999, 2010, 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 "incls/_precompiled.incl"

#include "incls/_c1_Optimizer.cpp.incl"

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

 public:

    _has_substitution = false;

    _hir->iterate_preorder(this);

    if (_has_substitution) {

      SubstitutionResolver sr(_hir);

    }

  }

  int cee_count() const                          { return _cee_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);

      }

    }

  }

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

    cur_end = cur_end->set_next(result);

    }

  }

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

};

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

  BlockList*        _work_list;                   // Basic blocks to visit

  bool visitable(Value x) {

    assert(_visitable_instructions != NULL, "check");

    return _visitable_instructions->contains(x);

  }

  void mark_visited(Value x) {