/*

 * Copyright (c) 1998, 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 "ci/ciMethodData.hpp"

#include "compiler/compileLog.hpp"

#include "libadt/vectset.hpp"

#include "memory/allocation.inline.hpp"

#include "memory/resourceArea.hpp"

#include "opto/addnode.hpp"

#include "opto/callnode.hpp"

#include "opto/connode.hpp"

#include "opto/convertnode.hpp"

#include "opto/divnode.hpp"

#include "opto/idealGraphPrinter.hpp"

#include "opto/loopnode.hpp"

#include "opto/mulnode.hpp"

#include "opto/rootnode.hpp"

#include "opto/superword.hpp"

//=============================================================================

//------------------------------is_loop_iv-------------------------------------

// Determine if a node is Counted loop induction variable.

// The method is declared in node.hpp.

const Node* Node::is_loop_iv() const {

  if (this->is_Phi() && !this->as_Phi()->is_copy() &&

      this->as_Phi()->region()->is_CountedLoop() &&

      this->as_Phi()->region()->as_CountedLoop()->phi() == this) {

    return this;

  } else {

    return NULL;

  }

}

//=============================================================================

//------------------------------dump_spec--------------------------------------

// Dump special per-node info

#ifndef PRODUCT

void LoopNode::dump_spec(outputStream *st) const {

  if (is_inner_loop()) st->print( "inner " );

  if (is_partial_peel_loop()) st->print( "partial_peel " );

  if (partial_peel_has_failed()) st->print( "partial_peel_failed " );

}

#endif

//------------------------------is_valid_counted_loop-------------------------

bool LoopNode::is_valid_counted_loop() const {

  if (is_CountedLoop()) {

    CountedLoopNode*    l  = as_CountedLoop();

    CountedLoopEndNode* le = l->loopexit_or_null();

    if (le != NULL &&

        le->proj_out_or_null(1 /* true */) == l->in(LoopNode::LoopBackControl)) {

      Node* phi  = l->phi();

      Node* exit = le->proj_out_or_null(0 /* false */);

      if (exit != NULL && exit->Opcode() == Op_IfFalse &&

          phi != NULL && phi->is_Phi() &&

          phi->in(LoopNode::LoopBackControl) == l->incr() &&

          le->loopnode() == l && le->stride_is_con()) {

        return true;

      }

    }

  }

  return false;

}

//------------------------------get_early_ctrl---------------------------------

// Compute earliest legal control

Node *PhaseIdealLoop::get_early_ctrl( Node *n ) {

  assert( !n->is_Phi() && !n->is_CFG(), "this code only handles data nodes" );

  uint i;

  Node *early;

  if (n->in(0) && !n->is_expensive()) {

    early = n->in(0);

    if (!early->is_CFG()) // Might be a non-CFG multi-def

      early = get_ctrl(early);        // So treat input as a straight data input

    i = 1;

  } else {

    early = get_ctrl(n->in(1));

    i = 2;

  }

  uint e_d = dom_depth(early);

  assert( early, "" );

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

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

    assert( cin, "" );

    // Keep deepest dominator depth

    uint c_d = dom_depth(cin);

    if (c_d > e_d) {           // Deeper guy?

      early = cin;              // Keep deepest found so far

      e_d = c_d;

    } else if (c_d == e_d &&    // Same depth?

               early != cin) { // If not equal, must use slower algorithm

      // If same depth but not equal, one _must_ dominate the other

      // and we want the deeper (i.e., dominated) guy.

      Node *n1 = early;

      Node *n2 = cin;

      while (1) {

        n1 = idom(n1);          // Walk up until break cycle

        n2 = idom(n2);

        if (n1 == cin ||        // Walked early up to cin

            dom_depth(n2) < c_d)

          break;                // early is deeper; keep him

        if (n2 == early ||      // Walked cin up to early

            dom_depth(n1) < c_d) {

          early = cin;          // cin is deeper; keep him

          break;

        }

      }

      e_d = dom_depth(early);   // Reset depth register cache

    }

  }

  // Return earliest legal location

  assert(early == find_non_split_ctrl(early), "unexpected early control");

  if (n->is_expensive() && !_verify_only && !_verify_me) {

    assert(n->in(0), "should have control input");

    early = get_early_ctrl_for_expensive(n, early);

  }

  return early;

}

//------------------------------get_early_ctrl_for_expensive---------------------------------

// Move node up the dominator tree as high as legal while still beneficial

Node *PhaseIdealLoop::get_early_ctrl_for_expensive(Node *n, Node* earliest) {

  assert(n->in(0) && n->is_expensive(), "expensive node with control input here");

  assert(OptimizeExpensiveOps, "optimization off?");

  Node* ctl = n->in(0);

  assert(ctl->is_CFG(), "expensive input 0 must be cfg");

  uint min_dom_depth = dom_depth(earliest);

#ifdef ASSERT

  if (!is_dominator(ctl, earliest) && !is_dominator(earliest, ctl)) {

    dump_bad_graph("Bad graph detected in get_early_ctrl_for_expensive", n, earliest, ctl);

    assert(false, "Bad graph detected in get_early_ctrl_for_expensive");

  }

#endif

  if (dom_depth(ctl) < min_dom_depth) {

    return earliest;

  }

  while (1) {

    Node *next = ctl;

    // Moving the node out of a loop on the projection of a If

    // confuses loop predication. So once we hit a Loop in a If branch

    // that doesn't branch to an UNC, we stop. The code that process

    // expensive nodes will notice the loop and skip over it to try to

    // move the node further up.

    if (ctl->is_CountedLoop() && ctl->in(1) != NULL && ctl->in(1)->in(0) != NULL && ctl->in(1)->in(0)->is_If()) {

      if (!ctl->in(1)->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none)) {

        break;

      }

      next = idom(ctl->in(1)->in(0));

    } else if (ctl->is_Proj()) {

      // We only move it up along a projection if the projection is

      // the single control projection for its parent: same code path,

      // if it's a If with UNC or fallthrough of a call.

      Node* parent_ctl = ctl->in(0);

      if (parent_ctl == NULL) {

        break;

      } else if (parent_ctl->is_CountedLoopEnd() && parent_ctl->as_CountedLoopEnd()->loopnode() != NULL) {

        next = parent_ctl->as_CountedLoopEnd()->loopnode()->init_control();

      } else if (parent_ctl->is_If()) {

        if (!ctl->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none)) {

          break;

        }

        assert(idom(ctl) == parent_ctl, "strange");

        next = idom(parent_ctl);

      } else if (ctl->is_CatchProj()) {

        if (ctl->as_Proj()->_con != CatchProjNode::fall_through_index) {

          break;

        }

        assert(parent_ctl->in(0)->in(0)->is_Call(), "strange graph");

        next = parent_ctl->in(0)->in(0)->in(0);

      } else {

        // Check if parent control has a single projection (this

        // control is the only possible successor of the parent

        // control). If so, we can try to move the node above the

        // parent control.

        int nb_ctl_proj = 0;

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

          Node *p = parent_ctl->fast_out(i);

          if (p->is_Proj() && p->is_CFG()) {

            nb_ctl_proj++;

            if (nb_ctl_proj > 1) {

              break;

            }

          }

        }

        if (nb_ctl_proj > 1) {

          break;

        }

        assert(parent_ctl->is_Start() || parent_ctl->is_MemBar() || parent_ctl->is_Call(), "unexpected node");

        assert(idom(ctl) == parent_ctl, "strange");

        next = idom(parent_ctl);

      }

    } else {

      next = idom(ctl);

    }

    if (next->is_Root() || next->is_Start() || dom_depth(next) < min_dom_depth) {

      break;

    }

    ctl = next;

  }

  if (ctl != n->in(0)) {

    _igvn.replace_input_of(n, 0, ctl);

    _igvn.hash_insert(n);

  }

  return ctl;

}

//------------------------------set_early_ctrl---------------------------------

// Set earliest legal control

void PhaseIdealLoop::set_early_ctrl( Node *n ) {

  Node *early = get_early_ctrl(n);

  // Record earliest legal location

  set_ctrl(n, early);

}

//------------------------------set_subtree_ctrl-------------------------------

// set missing _ctrl entries on new nodes

void PhaseIdealLoop::set_subtree_ctrl( Node *n ) {

  // Already set?  Get out.

  if( _nodes[n->_idx] ) return;

  // Recursively set _nodes array to indicate where the Node goes

  uint i;

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

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

    if( m && m != C->root() )

      set_subtree_ctrl( m );

  }

  // Fixup self

  set_early_ctrl( n );

}

// Create a skeleton strip mined outer loop: a Loop head before the

// inner strip mined loop, a safepoint and an exit condition guarded

// by an opaque node after the inner strip mined loop with a backedge

// to the loop head. The inner strip mined loop is left as it is. Only

// once loop optimizations are over, do we adjust the inner loop exit

// condition to limit its number of iterations, set the outer loop

// exit condition and add Phis to the outer loop head. Some loop

// optimizations that operate on the inner strip mined loop need to be

// aware of the outer strip mined loop: loop unswitching needs to

// clone the outer loop as well as the inner, unrolling needs to only

// clone the inner loop etc. No optimizations need to change the outer

// strip mined loop as it is only a skeleton.

IdealLoopTree* PhaseIdealLoop::create_outer_strip_mined_loop(BoolNode *test, Node *cmp, Node *init_control,

                                                             IdealLoopTree* loop, float cl_prob, float le_fcnt,

                                                             Node*& entry_control, Node*& iffalse) {

  Node* outer_test = _igvn.intcon(0);

  set_ctrl(outer_test, C->root());

  Node *orig = iffalse;

  iffalse = iffalse->clone();

  _igvn.register_new_node_with_optimizer(iffalse);

  set_idom(iffalse, idom(orig), dom_depth(orig));

  IfNode *outer_le = new OuterStripMinedLoopEndNode(iffalse, outer_test, cl_prob, le_fcnt);

  Node *outer_ift = new IfTrueNode (outer_le);

  Node* outer_iff = orig;

  _igvn.replace_input_of(outer_iff, 0, outer_le);

  LoopNode *outer_l = new OuterStripMinedLoopNode(C, init_control, outer_ift);

  entry_control = outer_l;

  IdealLoopTree* outer_ilt = new IdealLoopTree(this, outer_l, outer_ift);

  IdealLoopTree* parent = loop->_parent;

  IdealLoopTree* sibling = parent->_child;

  if (sibling == loop) {

    parent->_child = outer_ilt;

  } else {

    while (sibling->_next != loop) {

      sibling = sibling->_next;

    }

    sibling->_next = outer_ilt;

  }

  outer_ilt->_next = loop->_next;

  outer_ilt->_parent = parent;

  outer_ilt->_child = loop;

  outer_ilt->_nest = loop->_nest;

  loop->_parent = outer_ilt;

  loop->_next = NULL;

  loop->_nest++;

  set_loop(iffalse, outer_ilt);

  register_control(outer_le, outer_ilt, iffalse);

  register_control(outer_ift, outer_ilt, outer_le);

  set_idom(outer_iff, outer_le, dom_depth(outer_le));

  _igvn.register_new_node_with_optimizer(outer_l);

  set_loop(outer_l, outer_ilt);

  set_idom(outer_l, init_control, dom_depth(init_control)+1);

  return outer_ilt;

}

//------------------------------is_counted_loop--------------------------------

bool PhaseIdealLoop::is_counted_loop(Node* x, IdealLoopTree*& loop) {

  PhaseGVN *gvn = &_igvn;

  // Counted loop head must be a good RegionNode with only 3 not NULL

  // control input edges: Self, Entry, LoopBack.

  if (x->in(LoopNode::Self) == NULL || x->req() != 3 || loop->_irreducible) {

    return false;

  }

  Node *init_control = x->in(LoopNode::EntryControl);

  Node *back_control = x->in(LoopNode::LoopBackControl);

  if (init_control == NULL || back_control == NULL)    // Partially dead

    return false;

  // Must also check for TOP when looking for a dead loop

  if (init_control->is_top() || back_control->is_top())

    return false;

  // Allow funny placement of Safepoint

  if (back_control->Opcode() == Op_SafePoint) {

    if (LoopStripMiningIter != 0) {

      // Leaving the safepoint on the backedge and creating a

      // CountedLoop will confuse optimizations. We can't move the

      // safepoint around because its jvm state wouldn't match a new

      // location. Give up on that loop.

      return false;

    }

    back_control = back_control->in(TypeFunc::Control);

  }

  // Controlling test for loop

  Node *iftrue = back_control;

  uint iftrue_op = iftrue->Opcode();

  if (iftrue_op != Op_IfTrue &&

      iftrue_op != Op_IfFalse)

    // I have a weird back-control.  Probably the loop-exit test is in

    // the middle of the loop and I am looking at some trailing control-flow

    // merge point.  To fix this I would have to partially peel the loop.

    return false; // Obscure back-control

  // Get boolean guarding loop-back test

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

  if (get_loop(iff) != loop || !iff->in(1)->is_Bool())

    return false;

  BoolNode *test = iff->in(1)->as_Bool();

  BoolTest::mask bt = test->_test._test;

  float cl_prob = iff->as_If()->_prob;

  if (iftrue_op == Op_IfFalse) {

    bt = BoolTest(bt).negate();

    cl_prob = 1.0 - cl_prob;

  }

  // Get backedge compare

  Node *cmp = test->in(1);

  int cmp_op = cmp->Opcode();

  if (cmp_op != Op_CmpI)

    return false;                // Avoid pointer & float compares

  // Find the trip-counter increment & limit.  Limit must be loop invariant.

  Node *incr  = cmp->in(1);

  Node *limit = cmp->in(2);

  // ---------

  // need 'loop()' test to tell if limit is loop invariant

  // ---------

  if (!is_member(loop, get_ctrl(incr))) { // Swapped trip counter and limit?

    Node *tmp = incr;            // Then reverse order into the CmpI

    incr = limit;

    limit = tmp;

    bt = BoolTest(bt).commute(); // And commute the exit test

  }

  if (is_member(loop, get_ctrl(limit))) // Limit must be loop-invariant

    return false;

  if (!is_member(loop, get_ctrl(incr))) // Trip counter must be loop-variant

    return false;

  Node* phi_incr = NULL;

  // Trip-counter increment must be commutative & associative.

  if (incr->Opcode() == Op_CastII) {

    incr = incr->in(1);

  }

  if (incr->is_Phi()) {

    if (incr->as_Phi()->region() != x || incr->req() != 3)

      return false; // Not simple trip counter expression

    phi_incr = incr;

    incr = phi_incr->in(LoopNode::LoopBackControl); // Assume incr is on backedge of Phi

    if (!is_member(loop, get_ctrl(incr))) // Trip counter must be loop-variant

      return false;

  }

  Node* trunc1 = NULL;

  Node* trunc2 = NULL;

  const TypeInt* iv_trunc_t = NULL;

  if (!(incr = CountedLoopNode::match_incr_with_optional_truncation(incr, &trunc1, &trunc2, &iv_trunc_t))) {

    return false; // Funny increment opcode

  }

  assert(incr->Opcode() == Op_AddI, "wrong increment code");

  // Get merge point

  Node *xphi = incr->in(1);

  Node *stride = incr->in(2);

  if (!stride->is_Con()) {     // Oops, swap these

    if (!xphi->is_Con())       // Is the other guy a constant?

      return false;             // Nope, unknown stride, bail out

    Node *tmp = xphi;           // 'incr' is commutative, so ok to swap

    xphi = stride;

    stride = tmp;

  }

  if (xphi->Opcode() == Op_CastII) {

    xphi = xphi->in(1);

  }

  // Stride must be constant

  int stride_con = stride->get_int();

  if (stride_con == 0)

    return false; // missed some peephole opt

  if (!xphi->is_Phi())

    return false; // Too much math on the trip counter

  if (phi_incr != NULL && phi_incr != xphi)

    return false;

  PhiNode *phi = xphi->as_Phi();

  // Phi must be of loop header; backedge must wrap to increment

  if (phi->region() != x)

    return false;

  if ((trunc1 == NULL && phi->in(LoopNode::LoopBackControl) != incr) ||

      (trunc1 != NULL && phi->in(LoopNode::LoopBackControl) != trunc1)) {

    return false;

  }

  Node *init_trip = phi->in(LoopNode::EntryControl);

  // If iv trunc type is smaller than int, check for possible wrap.

  if (!TypeInt::INT->higher_equal(iv_trunc_t)) {

    assert(trunc1 != NULL, "must have found some truncation");

    // Get a better type for the phi (filtered thru if's)

    const TypeInt* phi_ft = filtered_type(phi);

    // Can iv take on a value that will wrap?

    //

    // Ensure iv's limit is not within "stride" of the wrap value.

    //

    // Example for "short" type

    //    Truncation ensures value is in the range -32768..32767 (iv_trunc_t)

    //    If the stride is +10, then the last value of the induction

    //    variable before the increment (phi_ft->_hi) must be

    //    <= 32767 - 10 and (phi_ft->_lo) must be >= -32768 to

    //    ensure no truncation occurs after the increment.

    if (stride_con > 0) {

      if (iv_trunc_t->_hi - phi_ft->_hi < stride_con ||

          iv_trunc_t->_lo > phi_ft->_lo) {

        return false;  // truncation may occur

      }

    } else if (stride_con < 0) {

      if (iv_trunc_t->_lo - phi_ft->_lo > stride_con ||

          iv_trunc_t->_hi < phi_ft->_hi) {

        return false;  // truncation may occur

      }

    }

    // No possibility of wrap so truncation can be discarded

    // Promote iv type to Int

  } else {

    assert(trunc1 == NULL && trunc2 == NULL, "no truncation for int");

  }

  // If the condition is inverted and we will be rolling

  // through MININT to MAXINT, then bail out.

  if (bt == BoolTest::eq || // Bail out, but this loop trips at most twice!

      // Odd stride

      (bt == BoolTest::ne && stride_con != 1 && stride_con != -1) ||

      // Count down loop rolls through MAXINT

      ((bt == BoolTest::le || bt == BoolTest::lt) && stride_con < 0) ||

      // Count up loop rolls through MININT

      ((bt == BoolTest::ge || bt == BoolTest::gt) && stride_con > 0)) {

    return false; // Bail out

  }

  const TypeInt* init_t = gvn->type(init_trip)->is_int();