/*

 * Copyright (c) 2011, 2013, 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 "opto/loopnode.hpp"

#include "opto/addnode.hpp"

#include "opto/callnode.hpp"

#include "opto/connode.hpp"

#include "opto/loopnode.hpp"

#include "opto/mulnode.hpp"

#include "opto/rootnode.hpp"

#include "opto/subnode.hpp"

/*

 * The general idea of Loop Predication is to insert a predicate on the entry

 * path to a loop, and raise a uncommon trap if the check of the condition fails.

 * The condition checks are promoted from inside the loop body, and thus

 * the checks inside the loop could be eliminated. Currently, loop predication

 * optimization has been applied to remove array range check and loop invariant

 * checks (such as null checks).

*/

//-------------------------------register_control-------------------------

void PhaseIdealLoop::register_control(Node* n, IdealLoopTree *loop, Node* pred) {

  assert(n->is_CFG(), "must be control node");

  _igvn.register_new_node_with_optimizer(n);

  loop->_body.push(n);

  set_loop(n, loop);

  // When called from beautify_loops() idom is not constructed yet.

  if (_idom != NULL) {

    set_idom(n, pred, dom_depth(pred));

  }

}

//------------------------------create_new_if_for_predicate------------------------

// create a new if above the uct_if_pattern for the predicate to be promoted.

//

//          before                                after

//        ----------                           ----------

//           ctrl                                 ctrl

//            |                                     |

//            |                                     |

//            v                                     v

//           iff                                 new_iff

//          /    \                                /      \

//         /      \                              /        \

//        v        v                            v          v

//  uncommon_proj cont_proj                   if_uct     if_cont

// \      |        |                           |          |

//  \     |        |                           |          |

//   v    v        v                           |          v

//     rgn       loop                          |         iff

//      |                                      |        /     \

//      |                                      |       /       \

//      v                                      |      v         v

// uncommon_trap                               | uncommon_proj cont_proj

//                                           \  \    |           |

//                                            \  \   |           |

//                                             v  v  v           v

//                                               rgn           loop

//                                                |

//                                                |

//                                                v

//                                           uncommon_trap

//

//

// We will create a region to guard the uct call if there is no one there.

// The true projecttion (if_cont) of the new_iff is returned.

// This code is also used to clone predicates to clonned loops.

ProjNode* PhaseIdealLoop::create_new_if_for_predicate(ProjNode* cont_proj, Node* new_entry,

                                                      Deoptimization::DeoptReason reason) {

  assert(cont_proj->is_uncommon_trap_if_pattern(reason), "must be a uct if pattern!");

  IfNode* iff = cont_proj->in(0)->as_If();

  ProjNode *uncommon_proj = iff->proj_out(1 - cont_proj->_con);

  Node     *rgn   = uncommon_proj->unique_ctrl_out();

  assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");

  uint proj_index = 1; // region's edge corresponding to uncommon_proj

  if (!rgn->is_Region()) { // create a region to guard the call

    assert(rgn->is_Call(), "must be call uct");

    CallNode* call = rgn->as_Call();

    IdealLoopTree* loop = get_loop(call);

    rgn = new (C) RegionNode(1);

    rgn->add_req(uncommon_proj);

    register_control(rgn, loop, uncommon_proj);

    _igvn.hash_delete(call);

    call->set_req(0, rgn);

    // When called from beautify_loops() idom is not constructed yet.

    if (_idom != NULL) {

      set_idom(call, rgn, dom_depth(rgn));

    }

  } else {

    // Find region's edge corresponding to uncommon_proj

    for (; proj_index < rgn->req(); proj_index++)

      if (rgn->in(proj_index) == uncommon_proj) break;

    assert(proj_index < rgn->req(), "sanity");

  }

  Node* entry = iff->in(0);

  if (new_entry != NULL) {

    // Clonning the predicate to new location.

    entry = new_entry;

  }

  // Create new_iff

  IdealLoopTree* lp = get_loop(entry);

  IfNode *new_iff = iff->clone()->as_If();

  new_iff->set_req(0, entry);

  register_control(new_iff, lp, entry);

  Node *if_cont = new (C) IfTrueNode(new_iff);

  Node *if_uct  = new (C) IfFalseNode(new_iff);

  if (cont_proj->is_IfFalse()) {

    // Swap

    Node* tmp = if_uct; if_uct = if_cont; if_cont = tmp;

  }

  register_control(if_cont, lp, new_iff);

  register_control(if_uct, get_loop(rgn), new_iff);

  // if_uct to rgn

  _igvn.hash_delete(rgn);

  rgn->add_req(if_uct);

  // When called from beautify_loops() idom is not constructed yet.

  if (_idom != NULL) {

    Node* ridom = idom(rgn);

    Node* nrdom = dom_lca(ridom, new_iff);

    set_idom(rgn, nrdom, dom_depth(rgn));

  }

  // If rgn has phis add new edges which has the same

  // value as on original uncommon_proj pass.

  assert(rgn->in(rgn->req() -1) == if_uct, "new edge should be last");

  bool has_phi = false;

  for (DUIterator_Fast imax, i = rgn->fast_outs(imax); i < imax; i++) {

    Node* use = rgn->fast_out(i);

    if (use->is_Phi() && use->outcnt() > 0) {

      assert(use->in(0) == rgn, "");

      _igvn.rehash_node_delayed(use);

      use->add_req(use->in(proj_index));

      has_phi = true;

    }

  }

  assert(!has_phi || rgn->req() > 3, "no phis when region is created");

  if (new_entry == NULL) {

    // Attach if_cont to iff

    _igvn.hash_delete(iff);

    iff->set_req(0, if_cont);

    if (_idom != NULL) {

      set_idom(iff, if_cont, dom_depth(iff));

    }

  }

  return if_cont->as_Proj();

}

//------------------------------create_new_if_for_predicate------------------------

// Create a new if below new_entry for the predicate to be cloned (IGVN optimization)

ProjNode* PhaseIterGVN::create_new_if_for_predicate(ProjNode* cont_proj, Node* new_entry,

                                                    Deoptimization::DeoptReason reason) {

  assert(new_entry != 0, "only used for clone predicate");

  assert(cont_proj->is_uncommon_trap_if_pattern(reason), "must be a uct if pattern!");

  IfNode* iff = cont_proj->in(0)->as_If();

  ProjNode *uncommon_proj = iff->proj_out(1 - cont_proj->_con);

  Node     *rgn   = uncommon_proj->unique_ctrl_out();

  assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");

  uint proj_index = 1; // region's edge corresponding to uncommon_proj

  if (!rgn->is_Region()) { // create a region to guard the call

    assert(rgn->is_Call(), "must be call uct");

    CallNode* call = rgn->as_Call();

    rgn = new (C) RegionNode(1);

    register_new_node_with_optimizer(rgn);

    rgn->add_req(uncommon_proj);

    hash_delete(call);

    call->set_req(0, rgn);

  } else {

    // Find region's edge corresponding to uncommon_proj

    for (; proj_index < rgn->req(); proj_index++)

      if (rgn->in(proj_index) == uncommon_proj) break;

    assert(proj_index < rgn->req(), "sanity");

  }

  // Create new_iff in new location.

  IfNode *new_iff = iff->clone()->as_If();

  new_iff->set_req(0, new_entry);

  register_new_node_with_optimizer(new_iff);

  Node *if_cont = new (C) IfTrueNode(new_iff);

  Node *if_uct  = new (C) IfFalseNode(new_iff);

  if (cont_proj->is_IfFalse()) {

    // Swap

    Node* tmp = if_uct; if_uct = if_cont; if_cont = tmp;

  }

  register_new_node_with_optimizer(if_cont);

  register_new_node_with_optimizer(if_uct);

  // if_uct to rgn

  hash_delete(rgn);

  rgn->add_req(if_uct);

  // If rgn has phis add corresponding new edges which has the same

  // value as on original uncommon_proj pass.

  assert(rgn->in(rgn->req() -1) == if_uct, "new edge should be last");

  bool has_phi = false;

  for (DUIterator_Fast imax, i = rgn->fast_outs(imax); i < imax; i++) {

    Node* use = rgn->fast_out(i);

    if (use->is_Phi() && use->outcnt() > 0) {

      rehash_node_delayed(use);

      use->add_req(use->in(proj_index));

      has_phi = true;

    }

  }

  assert(!has_phi || rgn->req() > 3, "no phis when region is created");

  return if_cont->as_Proj();

}

//--------------------------clone_predicate-----------------------

ProjNode* PhaseIdealLoop::clone_predicate(ProjNode* predicate_proj, Node* new_entry,

                                          Deoptimization::DeoptReason reason,

                                          PhaseIdealLoop* loop_phase,

                                          PhaseIterGVN* igvn) {

  ProjNode* new_predicate_proj;

  if (loop_phase != NULL) {

    new_predicate_proj = loop_phase->create_new_if_for_predicate(predicate_proj, new_entry, reason);

  } else {

    new_predicate_proj =       igvn->create_new_if_for_predicate(predicate_proj, new_entry, reason);

  }

  IfNode* iff = new_predicate_proj->in(0)->as_If();

  Node* ctrl  = iff->in(0);

  // Match original condition since predicate's projections could be swapped.

  assert(predicate_proj->in(0)->in(1)->in(1)->Opcode()==Op_Opaque1, "must be");

  Node* opq = new (igvn->C) Opaque1Node(igvn->C, predicate_proj->in(0)->in(1)->in(1)->in(1));

  igvn->C->add_predicate_opaq(opq);

  Node* bol = new (igvn->C) Conv2BNode(opq);

  if (loop_phase != NULL) {

    loop_phase->register_new_node(opq, ctrl);

    loop_phase->register_new_node(bol, ctrl);

  } else {

    igvn->register_new_node_with_optimizer(opq);

    igvn->register_new_node_with_optimizer(bol);

  }

  igvn->hash_delete(iff);

  iff->set_req(1, bol);

  return new_predicate_proj;

}

//--------------------------clone_loop_predicates-----------------------

// Interface from IGVN

Node* PhaseIterGVN::clone_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check) {

  return PhaseIdealLoop::clone_loop_predicates(old_entry, new_entry, clone_limit_check, NULL, this);

}

// Interface from PhaseIdealLoop

Node* PhaseIdealLoop::clone_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check) {

  return clone_loop_predicates(old_entry, new_entry, clone_limit_check, this, &this->_igvn);

}

// Clone loop predicates to cloned loops (peeled, unswitched, split_if).

Node* PhaseIdealLoop::clone_loop_predicates(Node* old_entry, Node* new_entry,

                                                bool clone_limit_check,

                                                PhaseIdealLoop* loop_phase,

                                                PhaseIterGVN* igvn) {

#ifdef ASSERT

  if (new_entry == NULL || !(new_entry->is_Proj() || new_entry->is_Region() || new_entry->is_SafePoint())) {

    if (new_entry != NULL)

      new_entry->dump();

    assert(false, "not IfTrue, IfFalse, Region or SafePoint");

  }

#endif

  // Search original predicates

  Node* entry = old_entry;

  ProjNode* limit_check_proj = NULL;

  if (LoopLimitCheck) {

    limit_check_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);

    if (limit_check_proj != NULL) {

      entry = entry->in(0)->in(0);

    }

  }

  if (UseLoopPredicate) {

    ProjNode* predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);

    if (predicate_proj != NULL) { // right pattern that can be used by loop predication

      // clone predicate

      new_entry = clone_predicate(predicate_proj, new_entry,

                                  Deoptimization::Reason_predicate,

                                  loop_phase, igvn);

      assert(new_entry != NULL && new_entry->is_Proj(), "IfTrue or IfFalse after clone predicate");

      if (TraceLoopPredicate) {

        tty->print("Loop Predicate cloned: ");

        debug_only( new_entry->in(0)->dump(); )

      }

    }

  }

  if (limit_check_proj != NULL && clone_limit_check) {

    // Clone loop limit check last to insert it before loop.

    // Don't clone a limit check which was already finalized

    // for this counted loop (only one limit check is needed).

    new_entry = clone_predicate(limit_check_proj, new_entry,

                                Deoptimization::Reason_loop_limit_check,

                                loop_phase, igvn);

    assert(new_entry != NULL && new_entry->is_Proj(), "IfTrue or IfFalse after clone limit check");

    if (TraceLoopLimitCheck) {

      tty->print("Loop Limit Check cloned: ");

      debug_only( new_entry->in(0)->dump(); )

    }

  }

  return new_entry;

}

//--------------------------skip_loop_predicates------------------------------

// Skip related predicates.

Node* PhaseIdealLoop::skip_loop_predicates(Node* entry) {

  Node* predicate = NULL;

  if (LoopLimitCheck) {

    predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);

    if (predicate != NULL) {

      entry = entry->in(0)->in(0);

    }

  }

  if (UseLoopPredicate) {

    predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);

    if (predicate != NULL) { // right pattern that can be used by loop predication

      IfNode* iff = entry->in(0)->as_If();

      ProjNode* uncommon_proj = iff->proj_out(1 - entry->as_Proj()->_con);

      Node* rgn = uncommon_proj->unique_ctrl_out();

      assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");

      entry = entry->in(0)->in(0);

      while (entry != NULL && entry->is_Proj() && entry->in(0)->is_If()) {

        uncommon_proj = entry->in(0)->as_If()->proj_out(1 - entry->as_Proj()->_con);

        if (uncommon_proj->unique_ctrl_out() != rgn)

          break;

        entry = entry->in(0)->in(0);

      }

    }

  }

  return entry;

}

//--------------------------find_predicate_insertion_point-------------------

// Find a good location to insert a predicate

ProjNode* PhaseIdealLoop::find_predicate_insertion_point(Node* start_c, Deoptimization::DeoptReason reason) {

  if (start_c == NULL || !start_c->is_Proj())

    return NULL;

  if (start_c->as_Proj()->is_uncommon_trap_if_pattern(reason)) {

    return start_c->as_Proj();

  }

  return NULL;

}

//--------------------------find_predicate------------------------------------

// Find a predicate

Node* PhaseIdealLoop::find_predicate(Node* entry) {

  Node* predicate = NULL;

  if (LoopLimitCheck) {

    predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);

    if (predicate != NULL) { // right pattern that can be used by loop predication

      return entry;

    }

  }

  if (UseLoopPredicate) {

    predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);

    if (predicate != NULL) { // right pattern that can be used by loop predication

      return entry;

    }

  }

  return NULL;

}

//------------------------------Invariance-----------------------------------

// Helper class for loop_predication_impl to compute invariance on the fly and

// clone invariants.

class Invariance : public StackObj {

  VectorSet _visited, _invariant;

  Node_Stack _stack;

  VectorSet _clone_visited;

  Node_List _old_new; // map of old to new (clone)

  IdealLoopTree* _lpt;

  PhaseIdealLoop* _phase;

  // Helper function to set up the invariance for invariance computation

  // If n is a known invariant, set up directly. Otherwise, look up the

  // the possibility to push n onto the stack for further processing.

  void visit(Node* use, Node* n) {

    if (_lpt->is_invariant(n)) { // known invariant

      _invariant.set(n->_idx);

    } else if (!n->is_CFG()) {

      Node *n_ctrl = _phase->ctrl_or_self(n);

      Node *u_ctrl = _phase->ctrl_or_self(use); // self if use is a CFG

      if (_phase->is_dominator(n_ctrl, u_ctrl)) {

        _stack.push(n, n->in(0) == NULL ? 1 : 0);

      }

    }

  }

  // Compute invariance for "the_node" and (possibly) all its inputs recursively

  // on the fly

  void compute_invariance(Node* n) {

    assert(_visited.test(n->_idx), "must be");

    visit(n, n);

    while (_stack.is_nonempty()) {

      Node*  n = _stack.node();

      uint idx = _stack.index();

      if (idx == n->req()) { // all inputs are processed

        _stack.pop();

        // n is invariant if it's inputs are all invariant

        bool all_inputs_invariant = true;

        for (uint i = 0; i < n->req(); i++) {

          Node* in = n->in(i);

          if (in == NULL) continue;

          assert(_visited.test(in->_idx), "must have visited input");

          if (!_invariant.test(in->_idx)) { // bad guy

            all_inputs_invariant = false;

            break;

          }

        }

        if (all_inputs_invariant) {

          _invariant.set(n->_idx); // I am a invariant too

        }

      } else { // process next input

        _stack.set_index(idx + 1);

        Node* m = n->in(idx);

        if (m != NULL && !_visited.test_set(m->_idx)) {

          visit(n, m);

        }

      }

    }

  }

  // Helper function to set up _old_new map for clone_nodes.

  // If n is a known invariant, set up directly ("clone" of n == n).

  // Otherwise, push n onto the stack for real cloning.

  void clone_visit(Node* n) {

    assert(_invariant.test(n->_idx), "must be invariant");

    if (_lpt->is_invariant(n)) { // known invariant

      _old_new.map(n->_idx, n);

    } else { // to be cloned

      assert(!n->is_CFG(), "should not see CFG here");

      _stack.push(n, n->in(0) == NULL ? 1 : 0);

    }

  }

  // Clone "n" and (possibly) all its inputs recursively

  void clone_nodes(Node* n, Node* ctrl) {

    clone_visit(n);

    while (_stack.is_nonempty()) {

      Node*  n = _stack.node();

      uint idx = _stack.index();

      if (idx == n->req()) { // all inputs processed, clone n!

        _stack.pop();

        // clone invariant node

        Node* n_cl = n->clone();

        _old_new.map(n->_idx, n_cl);

        _phase->register_new_node(n_cl, ctrl);

        for (uint i = 0; i < n->req(); i++) {

          Node* in = n_cl->in(i);

          if (in == NULL) continue;

          n_cl->set_req(i, _old_new[in->_idx]);

        }

      } else { // process next input

        _stack.set_index(idx + 1);

        Node* m = n->in(idx);

        if (m != NULL && !_clone_visited.test_set(m->_idx)) {

          clone_visit(m); // visit the input

        }

      }

    }

  }

 public:

  Invariance(Arena* area, IdealLoopTree* lpt) :

    _lpt(lpt), _phase(lpt->_phase),

    _visited(area), _invariant(area), _stack(area, 10 /* guess */),

    _clone_visited(area), _old_new(area)

  {}

  // Map old to n for invariance computation and clone

  void map_ctrl(Node* old, Node* n) {

    assert(old->is_CFG() && n->is_CFG(), "must be");

    _old_new.map(old->_idx, n); // "clone" of old is n

    _invariant.set(old->_idx);  // old is invariant

    _clone_visited.set(old->_idx);

  }

  // Driver function to compute invariance

  bool is_invariant(Node* n) {

    if (!_visited.test_set(n->_idx))

      compute_invariance(n);

    return (_invariant.test(n->_idx) != 0);

  }

  // Driver function to clone invariant

  Node* clone(Node* n, Node* ctrl) {

    assert(ctrl->is_CFG(), "must be");

    assert(_invariant.test(n->_idx), "must be an invariant");

    if (!_clone_visited.test(n->_idx))