/*

 * Copyright 1999-2006 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.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:

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

    _has_substitution = false;

    _hir->iterate_preorder(this);

    if (_has_substitution) {

      // substituted some phis so resolve the 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);

      }

    }

  }

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

    int bci = if_->bci();

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

      cur_end = cur_end->set_next(t_value, bci);

    }

    if (f_value == f_const) {

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

      cur_end = cur_end->set_next(f_value, bci);

    }

    // it is very unlikely that the condition can be statically decided

    // (this was checked previously by the Canonicalizer), so always

    // append IfOp

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

    cur_end = cur_end->set_next(result, bci);

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

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

    }

    goto_state = goto_state->copy();

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

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

    goto_->set_state(goto_state);

    // Steal the bci for the goto from the sux

    cur_end = cur_end->set_next(goto_, sux->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());

    }

    _hir->verify();

  }

};

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

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

          // match up inlining level

          end_state = end_state->pop_scope();

        }

        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, next->bci());

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

                  tsux = if_->fsux();

                  fsux = if_->tsux();

                }

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

                  prev->set_next(newif, if_->bci());

                  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_ProfileCounter (ProfileCounter*  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 {

 private:

  static NullCheckEliminator* _static_nce;

  static void                 do_value(Value* vp);

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

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

    _visitable_instructions->remove(x);

  }

  void mark_visitable(Value x) {

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

    _visitable_instructions->put(x);

  }

  void clear_visitable_state() {

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

    _visitable_instructions->clear();

  }

  ValueSet*         _set;                         // current state, propagated to subsequent BlockBegins

  ValueSetList      _block_states;                // BlockBegin null-check states for all processed blocks

  NullCheckVisitor  _visitor;

  NullCheck*        _last_explicit_null_check;

  bool set_contains(Value x)                      { assert(_set != NULL, "check"); return _set->contains(x); }

  void set_put     (Value x)                      { assert(_set != NULL, "check"); _set->put(x); }

  void set_remove  (Value x)                      { assert(_set != NULL, "check"); _set->remove(x); }

  BlockList* work_list()                          { return _work_list; }

  void iterate_all();

  void iterate_one(BlockBegin* block);

  ValueSet* state()                               { return _set; }

  void      set_state_from (ValueSet* state)      { _set->set_from(state); }

  ValueSet* state_for      (BlockBegin* block)    { return _block_states[block->block_id()]; }

  void      set_state_for  (BlockBegin* block, ValueSet* stack) { _block_states[block->block_id()] = stack; }

  // Returns true if caused a change in the block's state.

  bool      merge_state_for(BlockBegin* block,

                            ValueSet*   incoming_state);

 public:

  // constructor

  NullCheckEliminator(Optimizer* opt)

    : _opt(opt)

    , _set(new ValueSet())

    , _last_explicit_null_check(NULL)

    , _block_states(BlockBegin::number_of_blocks(), NULL)

    , _work_list(new BlockList()) {

    _visitable_instructions = new ValueSet();

    _visitor.set_eliminator(this);

  }

  Optimizer*  opt()                               { return _opt; }

  IR*         ir ()                               { return opt()->ir(); }

  // Process a graph

  void iterate(BlockBegin* root);

  // In some situations (like NullCheck(x); getfield(x)) the debug

  // information from the explicit NullCheck can be used to populate

  // the getfield, even if the two instructions are in different

  // scopes; this allows implicit null checks to be used but the

  // correct exception information to be generated. We must clear the

  // last-traversed NullCheck when we reach a potentially-exception-

  // throwing instruction, as well as in some other cases.

  void        set_last_explicit_null_check(NullCheck* check) { _last_explicit_null_check = check; }

  NullCheck*  last_explicit_null_check()                     { return _last_explicit_null_check; }

  Value       last_explicit_null_check_obj()                 { return (_last_explicit_null_check

                                                                         ? _last_explicit_null_check->obj()

                                                                         : NULL); }

  NullCheck*  consume_last_explicit_null_check() {

    _last_explicit_null_check->unpin(Instruction::PinExplicitNullCheck);

    _last_explicit_null_check->set_can_trap(false);

    return _last_explicit_null_check;

  }

  void        clear_last_explicit_null_check()               { _last_explicit_null_check = NULL; }

  // Handlers for relevant instructions