/*

 * Copyright (c) 2011, 2018, 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/convertnode.hpp"

#include "opto/loopnode.hpp"

#include "opto/matcher.hpp"

#include "opto/mulnode.hpp"

#include "opto/opaquenode.hpp"

#include "opto/rootnode.hpp"

#include "opto/subnode.hpp"

#include <fenv.h>

#include <math.h>

/*

 * 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 projection (if_cont) of the new_iff is returned.

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

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

                                                      Deoptimization::DeoptReason reason,

                                                      int opcode) {

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

    rgn->add_req(uncommon_proj);

    register_control(rgn, loop, uncommon_proj);

    _igvn.replace_input_of(call, 0, rgn);

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

    if (_idom != NULL) {

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

    }

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

      Node* n = uncommon_proj->fast_out(i);

      if (n->is_Load() || n->is_Store()) {

        _igvn.replace_input_of(n, 0, rgn);

        --i; --imax;

      }

    }

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

  if (opcode == Op_If) {

    new_iff = new IfNode(entry, iff->in(1), iff->_prob, iff->_fcnt);

  } else {

    assert(opcode == Op_RangeCheck, "no other if variant here");

    new_iff = new RangeCheckNode(entry, iff->in(1), iff->_prob, iff->_fcnt);

  }

  register_control(new_iff, lp, entry);

  Node *if_cont = new IfTrueNode(new_iff);

  Node *if_uct  = new 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_internal(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.replace_input_of(iff, 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,

                                                    int opcode) {

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

    register_new_node_with_optimizer(rgn);

    rgn->add_req(uncommon_proj);

    replace_input_of(call, 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 = NULL;

  if (opcode == Op_If) {

    new_iff = new IfNode(new_entry, iff->in(1), iff->_prob, iff->_fcnt);

  } else {

    assert(opcode == Op_RangeCheck, "no other if variant here");

    new_iff = new RangeCheckNode(new_entry, iff->in(1), iff->_prob, iff->_fcnt);

  }

  register_new_node_with_optimizer(new_iff);

  Node *if_cont = new IfTrueNode(new_iff);

  Node *if_uct  = new 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, Op_If);

  } else {

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

  }

  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 Opaque1Node(igvn->C, predicate_proj->in(0)->in(1)->in(1)->in(1));

  igvn->C->add_predicate_opaq(opq);

  Node* bol = new 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);

}

void PhaseIdealLoop::clone_loop_predicates_fix_mem(ProjNode* dom_proj , ProjNode* proj,

                                                   PhaseIdealLoop* loop_phase,

                                                   PhaseIterGVN* igvn) {

  Compile* C = NULL;

  if (loop_phase != NULL) {

    igvn = &loop_phase->igvn();

  }

  C = igvn->C;

  ProjNode* other_dom_proj = dom_proj->in(0)->as_Multi()->proj_out(1-dom_proj->_con);

  Node* dom_r = other_dom_proj->unique_ctrl_out();

  if (dom_r->is_Region()) {

    assert(dom_r->unique_ctrl_out()->is_Call(), "unc expected");

    ProjNode* other_proj = proj->in(0)->as_Multi()->proj_out(1-proj->_con);

    Node* r = other_proj->unique_ctrl_out();

    assert(r->is_Region() && r->unique_ctrl_out()->is_Call(), "cloned predicate should have caused region to be added");

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

      Node* dom_use = dom_r->fast_out(i);

      if (dom_use->is_Phi() && dom_use->bottom_type() == Type::MEMORY) {

        assert(dom_use->in(0) == dom_r, "");

        Node* phi = NULL;

        for (DUIterator_Fast jmax, j = r->fast_outs(jmax); j < jmax; j++) {

          Node* use = r->fast_out(j);

          if (use->is_Phi() && use->bottom_type() == Type::MEMORY &&

              use->adr_type() == dom_use->adr_type()) {

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

            assert(phi == NULL, "only one phi");

            phi = use;

          }

        }

        if (phi == NULL) {

          const TypePtr* adr_type = dom_use->adr_type();

          int alias = C->get_alias_index(adr_type);

          Node* call = r->unique_ctrl_out();

          Node* mem = call->in(TypeFunc::Memory);

          MergeMemNode* mm = NULL;

          if (mem->is_MergeMem()) {

            mm = mem->clone()->as_MergeMem();

            if (adr_type == TypePtr::BOTTOM) {

              mem = mem->as_MergeMem()->base_memory();

            } else {

              mem = mem->as_MergeMem()->memory_at(alias);

            }

          } else {

            mm = MergeMemNode::make(mem);

          }

          phi = PhiNode::make(r, mem, Type::MEMORY, adr_type);

          if (adr_type == TypePtr::BOTTOM) {

            mm->set_base_memory(phi);

          } else {

            mm->set_memory_at(alias, phi);

          }

          if (loop_phase != NULL) {

            loop_phase->register_new_node(mm, r);

            loop_phase->register_new_node(phi, r);

          } else {

            igvn->register_new_node_with_optimizer(mm);

            igvn->register_new_node_with_optimizer(phi);

          }

          igvn->replace_input_of(call, TypeFunc::Memory, mm);

        }

        igvn->replace_input_of(phi, r->find_edge(other_proj), dom_use->in(dom_r->find_edge(other_dom_proj)));

      }

    }

  }

}

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

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

  if (limit_check_proj != NULL) {

    entry = skip_loop_predicates(entry);

  }

  ProjNode* profile_predicate_proj = NULL;

  ProjNode* predicate_proj = NULL;

  if (UseProfiledLoopPredicate) {

    profile_predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_profile_predicate);

    if (profile_predicate_proj != NULL) {

      entry = skip_loop_predicates(entry);

    }

  }

  if (UseLoopPredicate) {

    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

    ProjNode* proj = clone_predicate(predicate_proj, new_entry,

                                     Deoptimization::Reason_predicate,

                                     loop_phase, igvn);

    assert(proj != NULL, "IfTrue or IfFalse after clone predicate");

    new_entry = proj;

    if (TraceLoopPredicate) {

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

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

    }

    if (profile_predicate_proj != NULL) {

      // A node that produces memory may be out of loop and depend on

      // a profiled predicates. In that case the memory state at the

      // end of profiled predicates and at the end of predicates are

      // not the same. The cloned predicates are dominated by the

      // profiled predicates but may have the wrong memory

      // state. Update it.

      clone_loop_predicates_fix_mem(profile_predicate_proj, proj, loop_phase, igvn);

    }

  }

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

    // clone predicate

    new_entry = clone_predicate(profile_predicate_proj, new_entry,

                                Deoptimization::Reason_profile_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) {

  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;

}

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

  Node* predicate = NULL;

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

  if (predicate != NULL) {

    entry = skip_loop_predicates(entry);

  }

  if (UseProfiledLoopPredicate) {

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

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

      entry = skip_loop_predicates(entry);

    }

  }

  if (UseLoopPredicate) {

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

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

      entry = skip_loop_predicates(entry);

    }

  }

  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;

  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